查找二进制搜索树中的范围内的数据值并按升序将其打印出来

Question

这是一项家庭作业。我需要递归遍历二叉搜索树，以查明节点的数据值是否落在一个范围内（包括），并按升序打印出来。

我的思考过程如下：要按升序打印数据值，我需要在搜索树上按顺序遍历。为了有效地遍历，如果一个节点的左边的子节点小于下面的值，并且节点的数据小于下面的值，那么程序应该停止遍历到左边。同样的道理，如果一个节点的右边的子节点大于上面的值，并且节点的数据大于上面的值，那么程序应该停止向右移动。

所以在这里不用我的实现，与错误：

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。有什么建议么？

Answer 1

if (leftChild != null && root.key > lower) { 
    root = leftChild; <---- Gotcha! 
    rangeSearchTree(root, lower, upper); 
} 
if (root.key >= lower && root.key <= upper) { 

您正在更改代码中间的root。您在第二个if评估root是不是通过作为参数，但其左孩子...

Answer 2

如果第二个是第一个，我认为这个问题应该解决。