오른쪽 및 왼쪽 자식 액세스가있는 노드 트리 순회

Question

트리를 탐색하여 내 배열에 대해 null 값을 얻으려고합니다. 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 
    } 
} 

의 입력을 받아, 나는 [] 얻고있다. 나는 또한 루핑을 시도했다.

if(root != null) { 
    queue.add(root); 
    } 

while(root.left != null) { 
    while(root.right != null) { 
     queue.add(root); 
     root = root.right; 
    } 
    queue.add(root); 
    root = root.left; 
} 

이것은 또한 작동하지 않는다. 이것 역시 나에게 [] 배열을 돌려 줄 것이다. 트리 탐색은 트리 높이 (레벨)로 표시된 트리 수준에서 왼쪽에서 오른쪽으로 트리를 인쇄해야합니다. 이견있는 사람?

Answer 1

... t = [1,2,4,3,5]를 반환해야하고 []지고 있습니다.

는

음,가 루프 당신이 채우는 데 사용하고있는 살펴 보자 당신의 Queue :

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

은 당신이 여기서하는 일은 queue.poll() 반환 null 때까지 반복하고, 우리는 보면 javadoc for ArrayDeque, 우리 poll()

취득 및 이 나타내지는 큐의 선두 제거 볼 deque (다른 말로 표현하면,이 양단 큐의 최초의 요소). 는,이 양단 큐가 하늘의 경우는 null를 돌려줍니다..

기본적으로 Queue이 비어있을 때까지 루핑 한 다음 반환 할 크기를 기반으로 배열을 만듭니다. 크기가 항상 0이기 때문에 항상 길이가 0 인 배열을 반환합니다.

선주문 탐색을 수행하는 것처럼 보이므로 proper algorithm을 사용하여 메소드를 다시 작성해야합니다.

비회원 순회를하는 경우 here's an algorithm 대신 그렇게하십시오.