Stack을 사용한 "inorder tree traversal"알고리즘 구현 수정

Question

이진 트리의 inorder 순회를위한 비 재귀 적 메서드를 구현해야한다는 것입니다. 나는 꼼짝 못한다.

public void inorder(BinaryTree v) { 
    Stack<BinaryTree> stack = new Stack<BinaryTree>(); 
    stack.push(v); 
    System.out.println(v.getValue()); 

    while(!stack.isEmpty()) { 
     while(v.getLeft() != null) { 
      v = v.getLeft(); 
      stack.push(v); 
      System.out.println(v.getValue()); 
     } 

     while(v.getRight() != null) { 
      v = v.getRight(); 
      stack.push(v); 
      System.out.println(v.getValue()); 
     } 
       stack.pop(); 
    } 
} 

내가 그것을 단지 내 나무, 예를 들어, 왼쪽을 출력 것으로 나타났습니다 : 여기에 지금까지 무엇을 가지고

  A 
     / \ 
     B  C 
    / \/\ 
    D  E F G 
/\ 
    H  I 
/\ 
J K 

이 A B D H J

Answer 1

이 코드에 따라, getLeft() 부분에 대한 while 루프는 모든 방법 트리의 왼쪽 아래로 간다 부여하고 종료합니다. v은 오른쪽 자식이없는 노드 J이므로 지금은 루프가 실행되지 않습니다.

하면이 코드 예제 시도해보십시오 http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow의 대답 :

이

Stack<Node> stack = new Stack<>(); 
Node current = root; 
while(current != null || !stack.isEmpty()){ 
    if(current != null){ 
    stack.push(current); 
    current = current.left; 
    } else if(!stack.isEmpty()) { 
    current = stack.pop(); 
    process(current); 
    current = current.right; 
    } 
} 

은 기본적으로 위의 코드를 왼쪽으로 진행시키고 : https://stackoverflow.com/a/12718147/1178781이

// Inorder traversal: 
// Keep the nodes in the path that are waiting to be visited 
Stack s = new Stack(); 
// The first node to be visited is the leftmost 
Node node = root; 
while (node != null) 
{ 
    s.push(node); 
    node = node.left; 
} 
// Traverse the tree 
while (s.size() > 0) 
{ 
    // Visit the top node 
    node = (Node)s.pop(); 
    System.out.println((String)node.data); 
    // Find the next node 
    if (node.right != null) 
    { 
     node = node.right; 
     // The next node to be visited is the leftmost 
     while (node != null) 
     { 
      s.push(node); 
      node = node.left; 
     } 
    } 
} 

Answer 2

당신은 크게 단일 동안 루프 위를 단순화 할 수 있습니다 분기의 가장 왼쪽 노드에 도달 할 때까지 스택에 분기합니다. 그런 다음 팝업하고 처리합니다 (인쇄하거나 다른 것으로 처리 할 수 ​​있음). 그러면 왼쪽 분기와 노드 자체가 완료된 이후로 처리 할 스택의 오른쪽 분기를 푸시합니다.

Answer 3

또 다른 간단한 이진 탐색 구현 :

import java.util.Stack; 

public class BinaryTree { 

    public static void main(String args[]) 
    { 
     Node root = Node.createDummyTree(); 
     Node tnode; //= root; 

     Stack<Node> stack = new Stack<Node>(); 

     if (root != null) 
     { 
      stack.push(root); 
     } 

     while (!stack.isEmpty()) 
     { 
      tnode = stack.pop(); 

      if (tnode != null) 
      { 
       System.out.println(tnode.value); 

       if(tnode.rightNode != null) 
       { 
        stack.push(tnode.rightNode); 
       } 

       if (tnode.leftNode != null) 
       { 
        stack.push(tnode.leftNode); 
       } 
      } 
     } 
    } 

} 

class Node { 
    public Node leftNode; 
    public Node rightNode; 
    public String value; 

    Node(String value) 
    { 
     this.value = value; 
    } 

    /** 
    * Construct a dummy binary Tree 
    *    A 
    *  /  \ 
    *   B   C 
    *  / \  / \ 
    *  D  E  F  G 
    * /\ /\ /\ /\ 
    * H I J K L M N O 

    * @return 
    */ 

    public static Node createDummyTree(){ 

     Node root = new Node("A"); 
     root.leftNode = new Node("B"); 
     root.rightNode = new Node("C"); 

     Node tnode = root.leftNode; 
     tnode.leftNode = new Node("D"); 
     tnode.rightNode = new Node("E"); 

     Node tempNode = tnode.rightNode; //remember "E" 

     tnode = tnode.leftNode; 
     tnode.leftNode = new Node ("H"); 
     tnode.rightNode = new Node ("I"); 

     tnode = tempNode; 

     tnode.leftNode = new Node ("J"); 
     tnode.rightNode = new Node ("K"); 

     tnode = root.rightNode; 
     tnode.leftNode = new Node("F"); 
     tnode.rightNode = new Node("G"); 

     tempNode = tnode.rightNode; // rememebr "G" 

     tnode = tnode.leftNode; 
     tnode.leftNode = new Node("L"); 
     tnode.rightNode = new Node("M"); 

     tnode = tempNode; 

     tnode.leftNode = new Node("N"); 
     tnode.rightNode = new Node("O"); 

     return root; 
    } 
} 

Answer 4

나는 오직 하나의 루프 동안 사용하는 해결책을 가지고 있습니다. 그것은 Giovanni의 솔루션과 비슷하지만 제 의견으로는 더 깨끗하고 읽기 쉽습니다. 특히, 디자인은 In Order Traversal의 재귀 적 솔루션과 유사하여 이해하기 쉽습니다.

public void InOrderTraversal(Node root) { 

    if (root == null) return; 

    Deque<Node> stack = new ArrayDeque<>(); 

    stack.push(root); 

    while (!stack.isEmpty()) { 

     Node curr = stack.peek(); 

     if (curr.left != null) { 

      stack.push(curr.left); 
      continue; 
     } 


     Node node_to_print = stack.pop(); 
     System.out.println(node_to_print.data); 


     if (curr.right != null) { 

      stack.push(curr.right); 

     } 

    } 

    return; 
} 

참고 : Deque 인터페이스를 사용하여 스택을 구현했습니다. API에 따르면이 방법이 선호됩니다. http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html