C语言二叉搜索树高效范围遍历优化方案求助

核心优化思路 #

利用二叉搜索树（BST）的特性：左子树节点值均小于当前节点，右子树节点值均大于当前节点。通过判断当前节点与上下界的关系，跳过不必要的子树遍历，大幅减少访问节点的数量。

优化后代码实现 #

// n - 当前节点
// l - 结果累加列表
static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    if (n == NULL) {
        return;
    } 

    int cmpLower = t->compare(n->rec, lower);
    int cmpUpper = t->compare(n->rec, upper);

    // 仅当当前节点 >= 下界时，左子树才可能存在符合条件的节点
    if (cmpLower >= 0) {
        doTreeSearchBetween(t, n->left, lower, upper, l);
    }

    // 当前节点在范围内则加入结果列表
    if (cmpLower >= 0 && cmpUpper <= 0) {
        ListAppend(l, n->rec);
    }

    // 仅当当前节点 <= 上界时，右子树才可能存在符合条件的节点
    if (cmpUpper <= 0) {
        doTreeSearchBetween(t, n->right, lower, upper, l);
    }
}

关键逻辑说明 #

• 左子树遍历判断：如果当前节点值小于下界（cmpLower < 0），其左子树所有节点值必然更小，不可能落在查询范围内，直接跳过左子树遍历。
• 右子树遍历判断：如果当前节点值大于上界（cmpUpper > 0），其右子树所有节点值必然更大，不可能落在查询范围内，直接跳过右子树遍历。
• 结果顺序一致性：保留原中序遍历的执行顺序（符合条件的左子树→当前节点→符合条件的右子树），保证结果列表与原全遍历的输出顺序一致（升序排列）。

效果验证 #

以你提供的测试用例为例：

Inserting: 11 13 17 19 23 29 31 37 41 43
Searching between 10 and 20
Search returned: 11 13 17 19

优化后会直接跳过23及后续的右子树节点，仅访问11、13、17、19及其空左子树，访问节点数大幅减少。

内容的提问来源于stack exchange，提问作者FreeAntiVirus