二叉链表实现二叉排序树c++

二叉链表是一种常用的数据结构，可以用来实现二叉排序树。二叉排序树是一种特殊的二叉树，它满足以下两个条件：

1. 左子树上所有节点的值都小于根节点的值；
2. 右子树上所有节点的值都大于根节点的值。

在C++中，我们可以通过定义一个二叉树结构体来实现二叉排序树。具体实现步骤如下：

1. 定义二叉树结构体：

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

2. 实现插入操作：

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

3. 实现查找操作：

bool search(TreeNode* root, int val) {
    if (!root) {
        return false;
    }
    if (root->val == val) {
        return true;
    } else if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

4. 实现删除操作：

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