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