You need to enable JavaScript to run this app. 如何实现带剪枝的BST成员函数打印[min,max]区间内所有节点
优惠活动
大模型
产品
解决方案
定价
更多

如何实现带剪枝的BST成员函数打印[min,max]区间内所有节点

BST区间打印函数的正确实现逻辑

现有代码的核心问题

你当前的实现存在几个无法绕过的硬伤:

  • 单游标的遍历架构从根本上无法处理“当前节点落在区间内时,需要同时遍历左右两个子树”的场景:当你把游标currNode移向左子树时,右子树中可能符合区间要求的节点会被完全丢弃,永远不会被访问到。
  • 存在多处空指针风险:代码中直接访问left_、right_的成员值,没有先判断指针是否为空,一旦孩子节点是空就会直接触发运行时崩溃。
  • 存在编译错误:打印语句中直接引用了data_,这是Node结构体的成员,不是printBetween函数的局部变量,无法通过编译,应该取当前节点的data_成员值。
  • 区间边界判断错误:要求打印闭区间[min, max]内的节点,但代码里用了data_ > min,会漏掉值恰好等于min的节点。
  • 空树判断逻辑不完整:当root_为空时打印了提示,但没有提前退出函数,后续代码依然会执行到空指针访问的逻辑。

核心遍历与剪枝规则

结合BST“左小右大”的性质,我们不需要遍历整棵树,只按照以下规则判断哪些子树需要访问,哪些直接剪枝丢弃:

  1. 如果当前节点值 小于min:它的整棵左子树所有值都比当前节点更小,必然全部小于min,完全没有遍历价值,只需要去遍历它的右子树(右子树值更大,才有可能落在目标区间内)。
  2. 如果当前节点值 大于max:它的整棵右子树所有值都比当前节点更大,必然全部大于max,完全没有遍历价值,只需要去遍历它的左子树(左子树值更小,才有可能落在目标区间内)。
  3. 如果当前节点值 落在[min, max]闭区间内:
    • 首先打印当前节点的值
    • 它的左、右子树都不能直接剪枝:左子树的值虽然比当前节点小,但可能大于min;右子树的值虽然比当前节点大,但可能小于max,两边都需要遍历。

两种合规的实现方式

两种实现都可以满足“printBetween对外接口入参固定,不需要传入待遍历节点指针”的要求:

方式1:类内私有递归辅助函数(最简洁)

因为对外暴露的printBetween接口签名是固定的,我们可以在类内部增加一个私有的辅助递归函数,传入当前待遍历的节点——这部分是类的内部实现细节,不会影响对外接口的定义。
完整实现代码:

// 类内私有辅助函数,不对外暴露
void printBetweenHelper(Node* node, int min, int max, bool& has_value) {
    if (node == nullptr) return;
    // 当前节点值过小,剪枝左子树,只遍历右子树
    if (node->data_ < min) {
        printBetweenHelper(node->right_, min, max, has_value);
        return;
    }
    // 当前节点值过大,剪枝右子树,只遍历左子树
    if (node->data_ > max) {
        printBetweenHelper(node->left_, min, max, has_value);
        return;
    }
    // 当前节点落在区间内,按中序顺序打印,同时遍历左右子树
    printBetweenHelper(node->left_, min, max, has_value);
    std::cout << "Value: " << node->data_ << "," << std::endl;
    has_value = true;
    printBetweenHelper(node->right_, min, max, has_value);
}

// 对外的固定接口,完全符合要求的入参格式
void printBetween(int min, int max) {
    bool has_value = false;
    printBetweenHelper(root_, min, max, has_value);
    if (!has_value) {
        std::cout << "No values found" << std::endl;
    }
}

方式2:迭代栈实现(不需要额外类成员)

如果不想增加私有辅助函数,完全可以在printBetween函数内部用栈存储待遍历的节点,按照剪枝规则决定哪些节点需要入栈,同样可以实现全部需求:

#include <stack>
void printBetween(int min, int max) {
    if (root_ == nullptr) {
        std::cout << "No values found" << std::endl;
        return;
    }
    bool has_value = false;
    std::stack<Node*> stk;
    stk.push(root_);
    while (!stk.empty()) {
        Node* curr = stk.top();
        stk.pop();
        if (curr == nullptr) continue;
        // 当前节点值过小,只需要压入右孩子(左子树全剪枝)
        if (curr->data_ < min) {
            stk.push(curr->right_);
            continue;
        }
        // 当前节点值过大,只需要压入左孩子(右子树全剪枝)
        if (curr->data_ > max) {
            stk.push(curr->left_);
            continue;
        }
        // 当前节点在区间内,打印,同时压入左右孩子
        std::cout << "Value: " << curr->data_ << "," << std::endl;
        has_value = true;
        stk.push(curr->right_);
        stk.push(curr->left_);
    }
    if (!has_value) {
        std::cout << "No values found" << std::endl;
    }
}

针对测试场景的验证

以目标区间min=9、max=20为例:

  • 遇到值为8的节点:小于min,整棵左子树的值都比8小,直接剪枝,只往右侧找更大的值
  • 遇到值为22的节点:大于max,整棵右子树的值都比22大,直接剪枝,只往左侧找更小的值
  • 遇到值为15的节点:落在区间内,打印后同时遍历左右子树,覆盖左子树中914的值、右子树中1620的值
    完全可以在不遍历全树的前提下,把所有符合区间的节点全部打印出来。

内容的提问来源于stack exchange,提问作者juice

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 21:24:04