"二叉搜索树(二叉排序树)是一种特殊的二叉树，其每个节点的左子树上的所有节点值都小于该节点值，而右子树上的所有节点值都大于该节点值。中序遍历二叉搜索树会得到一个递增序列。在二叉搜索树中查找后继和前驱结点有特定的方法：后继结点可以在右子树中找到最小值，或在上层中找到左孩子为当前节点的祖先；前驱结点则在左子树中找最大值，或在上层中找右孩子为当前节点的祖先。二叉搜索树适用于频繁的动态插入和查找操作，因为插入和查找的时间复杂度为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树和红黑树等。
我的内容管理
展开
