java - 二分探索木で範囲内にあるデータ値を見つけて、昇順で出力します

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コードの途中でを変更しています。root2番目に評価するのは、ifパラメーターとして渡されたものではなく、その左の子です...

Answer 2

2番目を最初のものにすれば、問題は解決するはずだと思います。