二叉树链式存储结构创建及基本运算

二叉树链式存储结构是通过指针实现的数据结构，每个节点包括一个数据域和两个指针域，分别指向左子树和右子树。下面是二叉树链式存储结构的创建及基本运算。

1. 创建二叉树

二叉树可以通过手动输入或者读入数据来创建。下面是手动输入创建二叉树的代码：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void createTree(TreeNode* &root) {
    int val;
    cin >> val;
    if (val == -1) {  // 输入-1表示该节点为空
        root = NULL;
    }
    else {
        root = new TreeNode(val);
        createTree(root->left);
        createTree(root->right);
    }
}

2. 遍历二叉树

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。下面是三种遍历方式的代码实现：

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

3. 插入节点

二叉树的插入操作是向二叉树中插入一个新节点。下面是插入操作的代码实现：

void insertNode(TreeNode* &root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertNode(root->left, val);
    }
    else {
        insertNode(root->right, val);
    }
}

4. 删除节点

二叉树的删除操作是将一个节点从二叉树中删除。删除操作需要考虑三种情况：删除的节点没有子节点、删除的节点有一个子节点、删除的节点有两个子节点。下面是删除操作的代码实现：

void deleteNode(TreeNode* &root, int val) {
    if (root == NULL) return;
    if (root->val == val) {
        if (root->left == NULL && root->right == NULL) {  // 没有子节点
            delete root;
            root = NULL;
        }
        else if (root->left == NULL || root->right == NULL) {  // 有一个子节点
            TreeNode* temp = root->left ? root->left : root->right;
            delete root;
            root = temp;
        }
        else {  // 有两个子节点
            TreeNode* temp = root->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            root->val = temp->val;
            deleteNode(root->right, temp->val);
        }
    }
    else if (val < root->val) {
        deleteNode(root->left, val);
    }
    else {
        deleteNode(root->right, val);
    }
}

以上是二叉树链式存储结构的创建及基本运算的代码实现。