C二叉搜索树BSTree如何使用

第一段：BSTree是什么

BSTree是Binary Search Tree的缩写，中文意思为二叉搜索树。BSTree是一种基于二叉树的数据结构，它的每个节点保存了一个关键字，它能够快速的将数据插入、查找、删除结点等操作，同时也支持中序遍历、前序遍历、后序遍历等操作。BSTree是一种自平衡的数据结构，它的时间复杂度接近于O(log n)，所以在一些需要高效处理大量数据的场景中使用广泛。

template 
class BinarySearchTree{
private:
    struct TreeNode{
        T val;
        TreeNode *left, *right;
        TreeNode(T x) : val(x), left(NULL), right(NULL) {}
    };
    TreeNode *root;
public:
    BinarySearchTree() : root(NULL) {}
    // 插入新节点
    void insert(T val) {
        if(!root) root = new TreeNode(val);
        else {
            TreeNode *cur = root;
            TreeNode *parent;
            while(cur){
                parent = cur;
                cur = val > cur->val ? cur->right : cur->left;
            }
            if(val > parent->val) parent->right = new TreeNode(val);
            else parent->left = new TreeNode(val);
        }
    }
    // 删除节点
    TreeNode* remove(TreeNode *root, T val) {
        if(root == NULL) return NULL;
        if(val > root->val){
            root->right = remove(root->right,val);
            return root;
        }
        if(val < root->val){
            root->left = remove(root->left,val);
            return root;
        }
        if(root->left == NULL && root->right == NULL){
            delete root;
            return NULL;
        }
        if(root->left == NULL || root->right == NULL){
            TreeNode *temp = root->left ? root->left : root->right;
            delete root;
            return temp;
        }
        TreeNode *cur = root->right;
        while(cur->left){
            cur = cur->left;
        }
        swap(root->val,cur->val);
        root->right = remove(root->right,val);
        return root;

    }
    ...
};

第二段：BSTree如何插入节点

BSTree的插入操作是将新元素插入到BSTree的合适位置，对于某个位置插入的节点，其左子树中所有节点的值肯定都比它小，右子树中所有节点的值肯定都比它大。因此，插入元素实际上是通过比较法，将元素不断插入到符合要求的位置。

    // 插入新节点
    void insert(T val) {
        if(!root) root = new TreeNode(val);
        else {
            TreeNode *cur = root;
            TreeNode *parent;
            while(cur){
                parent = cur;
                cur = val > cur->val ? cur->right : cur->left;
            }
            if(val > parent->val) parent->right = new TreeNode(val);
            else parent->left = new TreeNode(val);
        }
    }

第三段：BSTree如何删除节点

BSTree的删除操作分两种情况，一种是被删除节点没有子节点，一种是被删除节点有一个子节点或两个子节点。如果被删除节点没有子节点，那么直接删除即可；如果被删除节点有一个子节点，那么将子节点从删除节点删除后连接到删除节点的父节点即可；如果被删除节点有两个子节点，那么找到被删除节点右子树中的最小值节点，替换为被删除节点的值，然后再删除右子树中的最小值节点即可。

    // 删除节点
    TreeNode* remove(TreeNode *root, T val) {
        if(root == NULL) return NULL;
        if(val > root->val){
            root->right = remove(root->right,val);
            return root;
        }
        if(val < root->val){
            root->left = remove(root->left,val);
            return root;
        }
        if(root->left == NULL && root->right == NULL){
            delete root;
            return NULL;
        }
        if(root->left == NULL || root->right == NULL){
            TreeNode *temp = root->left ? root->left : root->right;
            delete root;
            return temp;
        }
        TreeNode *cur = root->right;
        while(cur->left){
            cur = cur->left;
        }
        swap(root->val,cur->val);
        root->right = remove(root->right,val);
        return root;
    }

第四段：BSTree的查找操作

BSTree的查找操作是从根节点开始，将待查找值与当前节点的值进行比较。如果待查找值小于当前节点的值，那么就去当前节点的左子树进行查找；如果待查找值大于当前值，那么就去右子树进行查找。如果找到了待查找值就返回当前节点，没找到则返回NULL。

    // 查找节点
    TreeNode* search(TreeNode* root, T val) {
        if(root == NULL) return NULL;
        if(root->val == val) return root;
        if(root->val > val) return search(root->left, val);
        else return search(root->right, val);
    }

总结

BSTree是一种基于二叉树的数据结构，它能够快速的将数据插入、查找、删除结点等操作，同时也支持中序遍历、前序遍历、后序遍历等操作。BSTree是一种自平衡的数据结构，可以用作有序数据容器和高效的查找工具。在实际应用中，需要注意BSTree的平衡性和对重复元素的处理。本文介绍了BSTree的插入、删除、查找等常用操作，并提供了相应的代码示例。