GB2-输出二叉搜索树中所有值大于 key 的结点
代码实现
| C |
|---|
| // 函数 func：输出二叉搜索树中所有值大于 key 的结点
// 参数说明：
// bt - 当前遍历的二叉树结点
// key - 比较的基准值
void func(BiTree bt, char key) {
// 递归终止条件：当前结点为空
if (bt != NULL) {
// 左子树递归：按照中序遍历，先访问左子树
func(bt->lchild, key);
// 根结点处理：判断当前结点值是否大于 key
if (bt->data > key) {
printf("%d ", bt->data); // 输出满足条件的结点值
}
// 右子树递归：访问右子树
func(bt->rchild, key);
}
}
|
代码逻辑解析
1. 二叉搜索树的性质
- 左子树：所有结点值 < 根结点值
- 右子树：所有结点值 > 根结点值
- 中序遍历：按升序访问所有结点
2. 算法核心思想
利用二叉搜索树的中序遍历特性：
- 中序遍历得到有序序列
- 输出所有大于 key 的元素
- 可以按升序输出结果
3. 执行流程图解
| Text Only |
|---|
| 二叉搜索树示例（key = 4）：
5
/ \
3 7
/ \ / \
2 4 6 8
/
1
中序遍历结果：1 2 3 4 5 6 7 8
大于4的值：5 6 7 8
执行过程：
访问1：1 ≤ 4，不输出
访问2：2 ≤ 4，不输出
访问3：3 ≤ 4，不输出
访问4：4 ≤ 4，不输出
访问5：5 > 4，输出5
访问6：6 > 4，输出6
访问7：7 > 4，输出7
访问8：8 > 4，输出8
|
4. 递归执行过程
| C |
|---|
| // 递归调用栈示意（以根结点5为例）：
// func(5)
// ├── func(3)
// │ ├── func(2)
// │ │ ├── func(1)
// │ │ │ └── 1 ≤ 4，不输出
// │ │ └── 2 ≤ 4，不输出
// │ ├── 3 ≤ 4，不输出
// │ └── func(4)
// │ └── 4 ≤ 4，不输出
// ├── 5 > 4，输出5
// └── func(7)
// ├── func(6)
// │ └── 6 > 4，输出6
// ├── 7 > 4，输出7
// └── func(8)
// └── 8 > 4，输出8
|
时间复杂度分析
1. 最坏情况
- 需要访问所有 N 个结点
- 每个结点都要进行比较操作
- 时间复杂度：O(N)
2. 最好情况
- 树中所有结点都 ≤ key
- 仍需访问所有结点进行比较
- 时间复杂度：O(N)
3. 平均情况
- 平均需要访问部分结点
- 但最坏情况仍为 O(N)
- 时间复杂度：O(N)
4. 总体时间复杂度
O(N)，其中 N 是树中结点总数
空间复杂度分析
1. 递归调用栈
- 递归深度等于树的高度
- 最坏情况（退化为链表）：O(N)
- 最好情况（完全平衡）：O(log N)
2. 额外空间
3. 总体空间复杂度
O(N)（最坏情况下的递归栈空间）
较难理解部分的说明
1. 为什么采用中序遍历？
| C |
|---|
| // 中序遍历的优势：输出结果有序
// 示例：key = 3
// 二叉搜索树：
// 5
// / \
// 3 7
// / \
// 6 8
// 中序遍历输出：3 5 6 7 8 → 大于3的值：5 6 7 8（有序）
// 先序遍历输出：5 3 7 6 8 → 大于3的值：5 7 6 8（无序）
// 后序遍历输出：3 6 8 7 5 → 大于3的值：6 8 7 5（无序）
|
2. 优化版本 - 提前终止
| C |
|---|
| // 优化思路：利用二叉搜索树性质提前剪枝
void func_optimized(BiTree bt, char key) {
if (bt != NULL) {
// 如果当前结点值大于key，才需要检查左子树
if (bt->data > key) {
func_optimized(bt->lchild, key);
printf("%d ", bt->data); // 输出当前结点
}
// 总是需要检查右子树（可能包含更大值）
func_optimized(bt->rchild, key);
}
}
// 更激进的优化版本
void func_advanced(BiTree bt, char key) {
if (bt != NULL) {
// 如果当前结点值小于等于key，只搜索右子树
if (bt->data <= key) {
func_advanced(bt->rchild, key);
} else {
// 如果当前结点值大于key，搜索左子树 + 输出 + 搜索右子树
func_advanced(bt->lchild, key);
printf("%d ", bt->data);
func_advanced(bt->rchild, key);
}
}
}
|
3. 执行轨迹对比
| C |
|---|
| // 原始版本 vs 优化版本（key = 4）
// 原始：访问所有8个结点
// 优化：可能减少访问次数
// 树结构：
// 5
// / \
// 3 7
// / \
// 6 8
// 原始版本访问顺序：1 2 3 4 5 6 7 8（8次访问）
// 优化版本访问顺序：3 5 6 7 8（5次访问）
|
延伸知识点
1. 非递归实现版本
| C |
|---|
| // 使用栈的非递归实现
void func_iterative(BiTree root, char key) {
stack<BiTree> stk;
BiTree current = root;
while (current != NULL || !stk.empty()) {
// 一直向左走到底
while (current != NULL) {
stk.push(current);
current = current->lchild;
}
// 处理栈顶结点
current = stk.top();
stk.pop();
// 判断是否大于key
if (current->data > key) {
printf("%d ", current->data);
}
// 转向右子树
current = current->rchild;
}
}
|
2. 范围查询扩展
| C |
|---|
| // 输出值在 [low, high] 范围内的所有结点
void range_query(BiTree bt, char low, char high) {
if (bt != NULL) {
// 只有当可能有满足条件的值时才访问左子树
if (bt->data > low) {
range_query(bt->lchild, low, high);
}
// 判断当前结点是否在范围内
if (bt->data >= low && bt->data <= high) {
printf("%d ", bt->data);
}
// 只有当可能有满足条件的值时才访问右子树
if (bt->data < high) {
range_query(bt->rchild, low, high);
}
}
}
// 输出值在 (key, +∞) 范围内的所有结点（不包括key）
void func_strict_greater(BiTree bt, char key) {
if (bt != NULL) {
if (bt->data > key) {
func_strict_greater(bt->lchild, key);
printf("%d ", bt->data);
}
func_strict_greater(bt->rchild, key);
}
}
|
3. 反向输出（降序）
| C |
|---|
| // 按降序输出大于key的值
void func_descending(BiTree bt, char key) {
if (bt != NULL) {
// 先访问右子树（大值）
func_descending(bt->rchild, key);
// 再处理当前结点
if (bt->data > key) {
printf("%d ", bt->data);
}
// 最后访问左子树（小值）
func_descending(bt->lchild, key);
}
}
|
4. 收集结果版本
| C |
|---|
| // 将结果收集到数组中
int collect_greater(BiTree bt, char key, int result[], int index) {
if (bt != NULL) {
index = collect_greater(bt->lchild, key, result, index);
if (bt->data > key) {
result[index++] = bt->data;
}
index = collect_greater(bt->rchild, key, result, index);
}
return index;
}
|
5. 计数版本
| C |
|---|
| // 统计大于key的结点个数
int count_greater(BiTree bt, char key) {
if (bt == NULL) return 0;
int count = 0;
if (bt->data > key) {
count = 1;
}
return count + count_greater(bt->lchild, key) + count_greater(bt->rchild, key);
}
// 或者更优化的版本
int count_greater_optimized(BiTree bt, char key) {
if (bt == NULL) return 0;
if (bt->data <= key) {
return count_greater_optimized(bt->rchild, key);
} else {
// 当前结点大于key，左子树中可能还有，右子树全部都大于key
return 1 + count_greater_optimized(bt->lchild, key) +
count_nodes(bt->rchild); // count_nodes统计子树结点数
}
}
|
6. 实际应用场景
| C |
|---|
| // 数据库索引范围查询
struct DatabaseIndex {
BiTree index_tree;
};
// 查找价格大于某个值的所有商品
void find_products_by_price(BiTree price_index, double min_price) {
printf("Products with price > %.2f:\n", min_price);
func(price_index, min_price);
}
// 查找年龄大于某个值的用户
void find_senior_users(BiTree age_index, int min_age) {
printf("Users with age > %d:\n", min_age);
func(age_index, min_age);
}
// 统计成绩优秀的学生
void find_excellent_students(BiTree score_index, int threshold) {
printf("Students with score > %d:\n", threshold);
func(score_index, threshold);
}
|
7. 理论扩展
数学性质分析：
| Text Only |
|---|
| 设二叉搜索树中共有N个结点，其中M个结点值大于key
时间复杂度分析：
- 原始算法：O(N) - 必须访问所有结点
- 优化算法：O(h + M) - h为树高，M为结果数量
- h：找到第一个大于key的结点所需时间
- M：输出M个结果所需时间
|
与快速选择算法的关系：
| C |
|---|
| // 快速选择找第k大的元素 vs 输出所有大于key的元素
// 共同点：都利用了有序性质
// 不同点：
// - 快速选择：找特定位置的元素
// - 当前算法：找满足条件的所有元素
|
在平衡树中的优化：
| C |
|---|
| // 在AVL树或红黑树中，由于高度保证O(log N)
// 优化版本的时间复杂度可以达到：O(log N + M)
// 其中M是满足条件的元素个数
|
8. 性能对比分析
| C |
|---|
| // 不同实现方式的性能对比：
// 1. 基础中序遍历：O(N) 时间，O(h) 空间
// 优点：实现简单，输出有序
// 缺点：必须访问所有结点
// 2. 优化递归版本：O(h + M) 时间，O(h) 空间
// 优点：可能减少访问结点数
// 缺点：实现稍复杂
// 3. 非递归版本：O(N) 时间，O(h) 空间
// 优点：避免递归栈溢出
// 缺点：需要额外栈空间
// 4. 增强树版本（维护子树大小）：O(log N + M) 时间
// 优点：最优时间复杂度
// 缺点：需要额外维护信息
|
这种方法体现了分治思想、数据结构特性利用和算法优化的完美结合。通过利用二叉搜索树的有序性质，将范围查询问题转化为有序遍历问题，是数据结构算法中的经典应用。同时展示了如何通过算法优化来提升实际性能。