二叉搜索树

二叉搜索树是一类特殊的二叉树，它满足中序遍历得到的结果为序列的顺序排序的特点，在对数据排序、查找等方面有着非常重要用途。

性质

二叉搜索树满足二叉树的所有性质，同时有着自身的特性。

中序遍历的结果为序列的顺序排序

节点的左子节点（以及左子树中所有元素）值小于节点的值；节点的右子节点（以及右子树中所有元素）值大于节点的值

从树根沿着左子树链数据依次减小，链的末尾为所有数据中的最小值

从树根沿着右子树链数据依次增大，链的末尾为所有数据中的最大值

查找和插入数据的平均时间复杂度为 O(

实现(c++)

struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    TreeNode(int d) :
        data(d), left(NULL), right(NULL), parent(NULL){};
};

//返回树中的最小元素节点
TreeNode* MinNode(TreeNode* root){
    TreeNode* node = root;
    while (node->left){
        node = node->left;
    }
    return node;
}
//返回树中最大元素节点
TreeNode* MaxNode(TreeNode* root){
    TreeNode* node = root;
    while (node->right){
        node = node->right;
    }
    return node;
}

//找出树中节点元素值等于给定值的节点
TreeNode* FindElement(TreeNode* root, int k){
    TreeNode* node = root;
    while (node){
        if (node->data == k){
            return node;
        }
        else if (node->data < k){
            node = node->left;
        }
        else{
            node = node->right;
        }
    }
    return node;
}

//向树中插入新元素
TreeNode* InsertElement(TreeNode* root, int k){
    TreeNode* node = root, *new_node;
    while (node){
        if (k > node->data){
            if (node->right == NULL){
                new_node = new TreeNode(k);
                node->right = new_node;
                new_node->parent = node;
                break;
            }
            node = node->right;
        }
        else{
            if (node->left == NULL){
                new_node = new TreeNode(k);
                node->left = new_node;
                new_node->parent = node;
                break;
            }
            node = node->left;
        }
    }
    return new_node;
}

//删除树中的元素
void DeleteNode(TreeNode* node){
    TreeNode* p = node->parent;
    if (p == NULL){
        return;
    }
    if (!node->left && !node->right){    //没有子节点
        if (p->left == node){
            p->left = NULL;
        }
        else{
            p->right = NULL;
        }
        delete node;
    }
    else if (node->left && !node->right){ //只有左子节点
        if (p->left == node){
            p->left = node->left;
        }
        else{
            p->right = node->left;
        }
        node->left->parent = p;
        delete node;
    }
    else if (!node->left && node->right){ //只有右子节点
        if (p->left == node){
            p->left = node->right;
        }
        else{
            p->right = node->right;
        }
        node->right->parent = p;
        delete node;
    }
    else{    //存在左右子节点： 先找到该节点的后继节点； 然后将该节点的内容替换为其后继节点的内容，再将后继节点删除
        TreeNode* suc = Successor(node);
        node->data = suc->data;
        DeleteNode(suc);
    }
}

//返回节点node的前驱节点（在中序遍历二叉搜索树时）
TreeNode* Predecessor(TreeNode* node){
    TreeNode* pre = NULL;
    if (node->left){        //如果该节点存在左子树，则返回其左子树中的最大节点
        return MaxNode(node->left);
    }
    else{
        pre = node->parent;
        while (pre){//如果不存在左子树，则沿着父节点向上寻找，直到找到最低的一个祖先节点，使得node节点在该祖先节点的右子树上
            if (pre->right == node){
                return pre;
            }
            node = pre;
            pre = node->parent;
        }
    }
    return pre;
}

//返回节点的后继节点（在中序遍历二叉搜索树时）
TreeNode* Successor(TreeNode* node){
    TreeNode* succ = NULL;
    if (node->right){        //如果节点存在右子树，则返回右子树中的最小节点
        return MinNode(node->right);
    }
    else{
        succ = node->parent;
        while (succ){//如果节点不存在右子树，则沿着父节点向上查找，直到某个祖先节点使得该节点位于该祖先节点的左子树上
            if (succ->left == node){
                return succ;
            }
            node = succ;
            succ = node->parent;
        }
    }
    return succ;
}