如何实现带剪枝的BST成员函数打印[min,max]区间内所有节点
BST区间打印函数的正确实现逻辑
现有代码的核心问题
你当前的实现存在几个无法绕过的硬伤:
- 单游标的遍历架构从根本上无法处理“当前节点落在区间内时,需要同时遍历左右两个子树”的场景:当你把游标
currNode移向左子树时,右子树中可能符合区间要求的节点会被完全丢弃,永远不会被访问到。 - 存在多处空指针风险:代码中直接访问
left_、right_的成员值,没有先判断指针是否为空,一旦孩子节点是空就会直接触发运行时崩溃。 - 存在编译错误:打印语句中直接引用了
data_,这是Node结构体的成员,不是printBetween函数的局部变量,无法通过编译,应该取当前节点的data_成员值。 - 区间边界判断错误:要求打印闭区间
[min, max]内的节点,但代码里用了data_ > min,会漏掉值恰好等于min的节点。 - 空树判断逻辑不完整:当
root_为空时打印了提示,但没有提前退出函数,后续代码依然会执行到空指针访问的逻辑。
核心遍历与剪枝规则
结合BST“左小右大”的性质,我们不需要遍历整棵树,只按照以下规则判断哪些子树需要访问,哪些直接剪枝丢弃:
- 如果当前节点值 小于min:它的整棵左子树所有值都比当前节点更小,必然全部小于min,完全没有遍历价值,只需要去遍历它的右子树(右子树值更大,才有可能落在目标区间内)。
- 如果当前节点值 大于max:它的整棵右子树所有值都比当前节点更大,必然全部大于max,完全没有遍历价值,只需要去遍历它的左子树(左子树值更小,才有可能落在目标区间内)。
- 如果当前节点值 落在[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
相关产品推荐
相关产品推荐

