二叉树的建立与基本操作

二叉树是一种树形结构，每个节点最多只有两个子节点，分别称为左子节点和右子节点。二叉树的建立可以通过递归或非递归方式实现。其中递归方式是最常用的方式之一，具体实现方法是：先创建一个根节点，然后递归创建左子树和右子树，直到所有节点都被创建完毕。非递归方式则需要借助栈来实现。

二叉树的基本操作包括遍历、插入、删除、查找等。其中遍历分为前序遍历、中序遍历和后序遍历三种方式。前序遍历是先遍历根节点，然后遍历左子树和右子树；序遍历是先遍历左子树，然后遍历根节点和右子树；后序遍历是先遍历左子树和右子树，然后遍历根节点。插入操作是将一个新节点插入到二叉树中的合适位置，删除操作是将一个节点从二叉树中删除，查找操作是在二叉树中查找一个节点是否存在。

下面是一些二叉树基本操作的代码实现：

- 二叉树的建立

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

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return NULL;
    }
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    vector<int>::iterator it = find(inorder.begin(), inorder.end(), rootVal);
    vector<int> leftInorder(inorder.begin(), it);
    vector<int> rightInorder(it + 1, inorder.end());
    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
    vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

- 前序遍历

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

- 中序遍历

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

- 后序遍历

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

- 插入操作

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

- 删除操作

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) {
        return NULL;
    }
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

- 查找操作

TreeNode* searchNode(TreeNode* root, int key) {
    if (root == NULL || root->val == key) {
        return root;
    }
    if (key < root->val) {
        return searchNode(root->left, key);
    } else {
        return searchNode(root->right, key);
    }
}