GB1-查找二叉排序树中第 k 小的结点¶

代码实现¶

C
// 函数 find：查找二叉排序树中第 k 小的结点
// 参数说明：
// bt - 当前遍历的二叉树结点
// k - 要查找的第 k 小（1-based）
// _count - 计数器指针，记录当前已访问的结点序号
// p - 结果指针，指向第 k 小的结点
void find(BiTree bt, int k, int* _count, BiTree* p) {
    // 递归终止条件：当前结点为空
    if (bt != NULL) {
        // 左子树递归：按照中序遍历，先访问左子树
        find(bt->lchild, k, _count, p);

        // 根结点处理：访问当前结点（中序遍历的核心）
        (*_count)++;  // 计数器加1，表示访问了第 *_count 个结点

        // 判断当前访问的结点是否为第 k 小的结点
        if ((*_count) == k) {
            *p = bt;  // 找到第 k 小的结点，保存到结果指针
        }

        // 右子树递归：访问右子树
        find(bt->rchild, k, _count, p);
    }
}

代码逻辑解析¶

1. 二叉排序树的性质¶

左子树：所有结点值 < 根结点值
右子树：所有结点值 > 根结点值
中序遍历：按升序访问所有结点

2. 算法核心思想¶

利用二叉排序树的中序遍历特性： - 中序遍历的结果是严格递增的序列 - 第 k 次访问的结点就是第 k 小的结点

3. 执行流程图解¶

Text Only

二叉排序树示例：
       5
      / \
     3   7
    / \ / \
   2  4 6  8
  /
 1

中序遍历过程：
访问顺序：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
计数：    1   2   3   4   5   6   7   8

查找第 4 小的结点：
- 访问第1小：1
- 访问第2小：2  
- 访问第3小：3
- 访问第4小：4 ← 找到目标

4. 递归执行过程¶

C
// 以查找第3小的结点为例
// 初始调用：find(root, 3, &count, &result)

// 递归调用栈示意：
// find(5) 
//   ├── find(3)
//   │   ├── find(2) 
//   │   │   ├── find(1)
//   │   │   │   └── count=1, *p=1
//   │   │   └── count=2, *p=2 ← 第2小
//   │   └── count=3, *p=3 ← 第3小（找到目标，可提前返回）
//   └── find(7) ← 后续调用可以优化剪枝

时间复杂度分析¶

1. 最坏情况¶

需要访问前 k 个结点
在最坏情况下 k = N（查找最大元素）
需要遍历整棵树
时间复杂度：O(N)

2. 最好情况¶

查找最小元素（k = 1）
只需访问最左路径上的结点
时间复杂度：O(h)，其中 h 是树的高度

3. 平均情况¶

平均需要访问 k 个结点
时间复杂度：O(k + h)

4. 总体时间复杂度¶

O(N)，其中 N 是树中结点总数

空间复杂度分析¶

1. 递归调用栈¶

递归深度等于树的高度
最坏情况（退化为链表）：O(N)
最好情况（完全平衡）：O(log N)

2. 额外空间¶

计数器指针：O(1)
结果指针：O(1)

3. 总体空间复杂度¶

O(N)（最坏情况下的递归栈空间）

较难理解部分的说明¶

1. 指针参数的设计¶

C
// 为什么使用指针参数？
void find(BiTree bt, int k, int* _count, BiTree* p) {
    // _count 是指针：需要在递归调用间共享计数状态
    // p 是指针：需要返回找到的结点地址
}

// 错误示例：
void find_wrong(BiTree bt, int k, int _count, BiTree p) {
    // _count 是值传递，无法在递归间共享状态
    // p 是值传递，无法返回结果
}

2. 中序遍历的正确性证明¶

C
// 二叉排序树中序遍历的性质证明：
// 1. 左子树中所有结点 < 根结点
// 2. 右子树中所有结点 > 根结点  
// 3. 左子树内部也满足二叉排序树性质
// 4. 右子树内部也满足二叉排序树性质

// 因此中序遍历（左→根→右）必然得到升序序列

3. 优化改进版本¶

C
// 优化版本：找到目标后提前返回，避免不必要的遍历
void find_optimized(BiTree bt, int k, int* _count, BiTree* p) {
    if (bt != NULL && *p == NULL) {  // 增加提前终止条件
        find_optimized(bt->lchild, k, _count, p);

        if (*p == NULL) {  // 只有还没找到才继续
            (*_count)++;
            if ((*_count) == k) {
                *p = bt;
                return;  // 找到后立即返回
            }

            find_optimized(bt->rchild, k, _count, p);
        }
    }
}

延伸知识点¶

1. 非递归实现版本¶

C
// 使用栈的非递归实现
BiTree find_iterative(BiTree root, int k) {
    stack<BiTree> stk;
    BiTree current = root;
    int count = 0;

    while (current != NULL || !stk.empty()) {
        // 一直向左走到底
        while (current != NULL) {
            stk.push(current);
            current = current->lchild;
        }

        // 处理栈顶结点
        current = stk.top();
        stk.pop();
        count++;

        if (count == k) {
            return current;  // 找到第k小的结点
        }

        // 转向右子树
        current = current->rchild;
    }

    return NULL;  // 未找到
}

2. 增强版二叉排序树¶

C
// 带有结点计数信息的二叉排序树结点定义
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
    int left_count;  // 左子树结点个数
} BiTNode, *BiTree;

// 利用计数信息的快速查找
BiTree find_with_count(BiTree root, int k) {
    if (root == NULL) return NULL;

    int left_size = root->left_count;

    if (k <= left_size) {
        return find_with_count(root->lchild, k);
    } else if (k == left_size + 1) {
        return root;
    } else {
        return find_with_count(root->rchild, k - left_size - 1);
    }
}
// 时间复杂度：O(h)，空间复杂度：O(h)

3. 相关查找问题¶

C
// 查找第 k 大的结点
void find_kth_largest(BiTree bt, int k, int* count, int total, BiTree* p) {
    if (bt != NULL && *p == NULL) {
        find_kth_largest(bt->rchild, k, count, total, p);

        if (*p == NULL) {
            (*count)++;
            if ((*count) == k) {
                *p = bt;
            }

            find_kth_largest(bt->lchild, k, count, total, p);
        }
    }
}

// 查找值在范围 [low, high] 内的所有结点
void find_range(BiTree bt, int low, int high) {
    if (bt != NULL) {
        if (bt->data >= low) {
            find_range(bt->lchild, low, high);
        }

        if (bt->data >= low && bt->data <= high) {
            printf("%d ", bt->data);
        }

        if (bt->data <= high) {
            find_range(bt->rchild, low, high);
        }
    }
}

4. 平衡二叉搜索树的应用¶

C
// 在AVL树或红黑树中，由于树高度保证为O(log N)
// 查找第k小元素的时间复杂度可以优化为：O(log N)
// 通过维护子树大小信息实现

// 结点结构扩展
struct AVLNode {
    int data;
    int height;
    int size;  // 以该结点为根的子树大小
    struct AVLNode *left, *right;
};

// 基于size信息的快速选择
AVLNode* select_kth(AVLNode* root, int k) {
    if (root == NULL || k <= 0 || k > root->size) {
        return NULL;
    }

    int left_size = (root->left) ? root->left->size : 0;

    if (k <= left_size) {
        return select_kth(root->left, k);
    } else if (k == left_size + 1) {
        return root;
    } else {
        return select_kth(root->right, k - left_size - 1);
    }
}

5. 实际应用场景¶

数据库索引：B+树中的范围查询和第k小查询
排行榜系统：查找第k名用户
统计分析：中位数、百分位数计算
内存管理：查找第k小的空闲块
算法竞赛：快速选择算法的树结构实现

6. 理论扩展¶

数学性质： - 二叉排序树的中序遍历与排序的关系 - 树的形态对查找效率的影响 - 最优二叉搜索树的构造

复杂度理论： - 比较排序的下界：Ω(N log N) - 选择问题的复杂度：O(N)（快速选择算法） - 有序结构上的查找优化

这种方法体现了分治思想和数据结构特性利用的完美结合，通过二叉排序树的有序性质，将查找第k小的问题转化为中序遍历的计数问题，是数据结构算法中的经典设计。