查找二進制搜索樹中的範圍內的數據值並按升序將其打印出來

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

如果第二個是第一個，我認爲這個問題應該解決。