右と左の子アクセスを持つノードツリーのトラバーサル

Question

ツリーを走査して、自分の配列のヌル値を取得しようとしています。 Nodeクラスのクラス定義で、ルートのない右と左の子にのみアクセスできるツリーを走査する必要があります。

class Tree<T> { 
Tree(T x) { 
    value = x; 
} 
T value; 
Tree<T> left; 
Tree<T> right; 
} 

public int[] traverseTree(Tree<Integer> t) { 
    Stack<Tree<Integer>> stack = new Stack<Tree<Integer>>(); 
    Tree<Integer> node = root; 

    while (node != null) { 
     stack.push(node); 
     node = node.left; 
    } 

    int[] result = new int[stack.size()]; 
    int i = 0; 
    while (stack.size() > 0) { 
     node = stack.pop(); 
     if(node != null) { 
      result[i] = node.value; 
      i++; 
     } 
     if (node.right != null) { 
      node = node.right; 

      while (node != null) { 
       stack.push(node); 
       node = node.left; 
      } 
     } 
    } 

    return result; 
} 

は、これは、[1,2,4,3,5]を返す必要があります

t = { 
"value": 1, 
"left": { 
    "value": 2, 
    "left": null, 
    "right": { 
     "value": 3, 
     "left": null, 
     "right": null 
    } 
}, 
"right": { 
    "value": 4, 
    "left": { 
     "value": 5, 
     "left": null, 
     "right": null 
    }, 
    "right": null 
    } 
} 

の入力を受け取り、私は[]取得しています。私も同様にループを試みました

これも機能しません。これも私に[]配列を返します。トラバーサルは、ツリーの高さ（レベル）によって示されるツリーレベルで、左から右にツリーを印刷する必要があります。何かご意見は？

Answer 1

... t = [1,2,4,3,5]に戻る必要があります。

さて、forループ、あなたのQueueを投入するために使用しているを見てみましょう：queue.poll()戻りnullまでループしているあなたがここでやっている

for (Tree<Integer> node = root; node != null; node = queue.poll()) { 
    //stuff 
} 

、と我々は見ている場合javadoc for ArrayDequeは、我々はpoll()

取得およびこのによって表されるキューの先頭を削除していることがわかりdeque（つまり、この両端キューの最初の要素）、またはがこの両端キューが空の場合はnullを返します。

したがって、基本的にはQueueが空になるまでループしてから、そのサイズに基づいて配列を作成して返します。そのサイズは常にゼロであるため、常に長さゼロの配列が返されます。

Preorderトラバーサルを探しているようですので、proper algorithmを使用してメソッドを書き直す必要があります。

非再帰的なトラバーサルがコミットされている場合は、そのようにしてhere's an algorithmを実行します。