这是一项家庭作业。我需要递归地遍历二叉搜索树,找出节点的数据值是否落在一个范围内(含),并按升序打印出来。
我的思考过程是:要按升序打印数据值,我需要在搜索树上进行中序遍历。为了高效地遍历,如果一个节点的左子节点小于下限值,并且该节点的数据小于下限值,则程序应该停止向左遍历。同样的道理,如果一个节点的右子节点大于上限值,并且该节点的数据大于上限值,则程序应该停止向右遍历。
这是我的实现,有错误:
public void rangeSearch(int lower, int upper) {
if (lower > upper)
throw new IllegalArgumentException("lower > upper");
if (root != null)
rangeSearchTree(root, lower, upper);
}
private static void rangeSearchTree(Node root, int lower, int upper) {
Node leftChild = root.left;
Node rightChild = root.right;
if (leftChild != null && root.key > lower) {
root = leftChild;
rangeSearchTree(root, lower, upper);
}
if (root.key >= lower && root.key <= upper) {
System.out.print(root.key + " ");
}
if (rightChild != null && root.key < upper) {
root = rightChild;
rangeSearchTree(root, lower, upper);
}
}
树的结构为:
7
/ \
5 9
/ \ /
2 6 8
\
4
当我输入 6
作为下限值,输入 9
作为上限值时,我得到 6 8 8
。正确答案应该是6 7 8 9
。有什么建议吗?
最佳答案
if (leftChild != null && root.key > lower) {
root = leftChild; <---- Gotcha!
rangeSearchTree(root, lower, upper);
}
if (root.key >= lower && root.key <= upper) {
您正在更改代码中间的root
。您在第二个 if
中计算的 root
不是作为参数传递的根,而是它的左子节点...
关于java - 在二叉搜索树中查找落在范围内的数据值并按升序打印它们,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13672463/