作为一种**动态查找表**，支持在数据频繁变动的情况下高效实现插入、删除和查找操作

一、二叉排序树的插入特性

1. 插入位置：新结点总是作为叶子结点插入。从根结点开始，比较关键字大小，若小于当前结点则进入左子树，否则进入右子树，直到找到空指针位置进行插入。此过程不涉及已有结点的移动，仅修改父结点的孩子指针，类似于有序链表中的“无移动插入”。
2. 形态依赖输入序列：二叉排序树的结构高度依赖于输入顺序。若输入序列为递增或递减（如12,18,23,45,60），则生成的树将退化为单枝树（即所有结点仅有右孩子或左孩子），导致树的高度达到n，查找、插入、删除操作的时间复杂度退化为O(n)，等同于顺序查找。

二、二叉排序树的删除操作
根据被删除结点*p的结构，分为三种情况处理：

1. p是叶子结点（且非根）

   • 操作简单：直接将其双亲结点*f的相应孩子指针置为空（f->lchild 或 f->rchild = NULL）。
   • 若p为根且是唯一结点，则删除后树为空。

2. p只有左子树或只有右子树

   • 将p的子树直接链接到其双亲结点*f的对应位置。
     • 例如：若p是f的左孩子且仅有右子树，则执行f->lchild = p->rchild。
   • 特殊情况：若p为根结点，则让其子树成为新的根。

3. p同时有左、右子树

   • 此时不能直接断开连接，需保持中序遍历的有序性。
   • 常用策略：
     • 找到*p的中序后继（即其右子树中的最小结点，也就是右子树中最左边的结点），或
     • 找到*p的中序前驱（即其左子树中的最大结点，也就是左子树中最右边的结点）。
   • 用该结点q的数据值替换p的数据值，然后按上述规则删除q（此时q必定属于前两种情况之一，因为它是极值结点，最多只有一个子树）。

补充：二叉排序树的核心作用

• 作为一种动态查找表，支持在数据频繁变动的情况下高效实现插入、删除和查找操作。
• 在理想情况下（树近似平衡），各项操作时间复杂度为O(log n)。
• 实际应用中易受输入序列影响而性能下降，因此常采用平衡二叉树（如AVL树、红黑树）来维持树的平衡，避免退化，从而保证稳定的对数级时间复杂度。

// 示例：二叉排序树节点定义structTreeNode{intval;structTreeNode*left;structTreeNode*right;};

在二叉排序树（BST）中，中序后继是指中序遍历序列中紧跟在指定节点之后的节点。实现中序后继查找需根据节点是否有右子树来分情况处理：

一、有右子树的情况

若目标节点p有右子树，则其中序后继是其右子树中的最左节点（即右子树中值最小的节点）。

步骤：

1. 进入p->right。
2. 沿左孩子一路向下，直到left为空。

structTreeNode*findInorderSuccessor(structTreeNode*p){structTreeNode*current=p->right;while(current&&current->left!=NULL){current=current->left;}returncurrent;}

二、无右子树的情况

若p没有右子树，则中序后继在其祖先中寻找：从根开始向下搜索，找到第一个“大于p->val”且“左子树包含p”的祖先节点。

方法：从根出发，用一个指针追踪可能的后继。

structTreeNode*findInorderSuccessorFromRoot(structTreeNode*root,structTreeNode*p){structTreeNode*successor=NULL;while(root!=NULL){if(p->val<root->val){successor=root;// 当前根可能是后继root=root->left;}else{root=root->right;}}returnsuccessor;}

注意：此方法适用于没有父指针的树结构。

三、带父指针的情况（优化）

如果每个节点含有指向父节点的指针（parent），可以向上回溯：

• 若p是其父节点的左孩子 → 父节点就是后继。
• 否则，一直向上找，直到当前节点是其父节点的左孩子为止，该父节点即为后继。

structTreeNode*findInorderSuccessorWithParent(structTreeNode*p){if(p->right){// 有右子树：找右子树中最左节点structTreeNode*current=p->right;while(current->left){current=current->left;}returncurrent;}else{// 无右子树：向上找第一个左分支的祖先structTreeNode*current=p;structTreeNode*parent=current->parent;while(parent!=NULL&&current==parent->right){current=parent;parent=parent->parent;}returnparent;}}

总结

时间复杂度：O(h)，h为树高；理想情况下 O(log n)，最坏 O(n)。