二叉搜索树：查找后继与前驱结点

"二叉搜索树(二叉排序树)是一种特殊的二叉树，其每个节点的左子树上的所有节点值都小于该节点值，而右子树上的所有节点值都大于该节点值。中序遍历二叉搜索树会得到一个递增序列。在二叉搜索树中查找后继和前驱结点有特定的方法：后继结点可以在右子树中找到最小值，或在上层中找到左孩子为当前节点的祖先；前驱结点则在左子树中找最大值，或在上层中找右孩子为当前节点的祖先。二叉搜索树适用于频繁的动态插入和查找操作，因为插入和查找的时间复杂度为O(h)，其中h是树的高度。" 在二叉搜索树的实现中，通常使用如下的C++结构来表示节点： ```cpp struct Node { int val; Node* lch; // 左孩子 Node* rch; // 右孩子 }; Node* root = NULL; // 根节点指针 ``` 插入新节点的函数`insert`通过比较新节点值与当前节点值，决定是在左子树还是右子树中插入，并递归进行，直到找到合适的位置。插入操作保持了二叉搜索树的性质。 ```cpp Node* insert(Node* p, int x) { if (p == NULL) { Node* q = new Node; q->val = x; q->lch = q->rch = NULL; return q; } else { if (x < p->val) p->lch = insert(p->lch, x); else p->rch = insert(p->rch, x); return p; } } ``` 为了输出二叉搜索树的节点，可以使用中序遍历，先遍历左子树，然后访问当前节点，最后遍历右子树。 ```cpp void print(Node* p) { if (p == NULL) return; print(p->lch); cout << p->val << ""; print(p->rch); } ``` 查找特定值的节点`find`同样通过比较值来决定在左子树还是右子树中继续查找，直到找到目标值或到达空节点。 ```cpp bool find(Node* p, int x) { if (p == NULL) return false; if (p->val == x) return true; if (p->val < x) return find(p->rch, x); else return find(p->lch, x); } ``` 查找最小和最大值的节点相当直观：最小值是根节点开始一直向左的叶节点，而最大值是从根节点开始一直向右的叶节点。 删除节点的操作较为复杂，需要根据被删除节点的子节点情况来处理。有以下三种情况： 1. 被删除节点没有左子节点，那么直接将右子节点提升到其位置。 2. 被删除节点的左子节点没有右子节点，将左子节点提升到其位置。 3. 前两种情况都不满足时，需要找到左子树中最大的节点（或右子树中最小的节点）来替换被删除节点。 二叉搜索树是一种重要的数据结构，尤其在需要高效地执行查找、插入和删除操作的场景下，例如数据库索引和动态排序。然而，当树失去平衡（比如退化成链表）时，性能会大幅下降。为了改善这种情况，可以使用自平衡二叉搜索树，如AVL树和红黑树等。