Исправление моей реализации алгоритма «обход дерева дерева» с помощью Stack

Question

Часть этого заключается в том, что я должен реализовать нерекурсивный метод обхода объекта в двоичном дереве. Я как бы застрял. Вот то, что я до сих пор:

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() части проходит весь путь вниз слева от дерева, а затем завершает свою работу. v теперь является узлом J, который не имеет дочернего элемента, поэтому следующий цикл while не запускается.

Попробуйте этот пример кода: http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow Ответ: 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

Вы можете значительно упростить выше с одного цикла While:

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; 
    } 
} 

В основном код выше выталкивает левый ветви в стеке, пока он не достигнет самого левого узла в ветке. Затем он всплывает и обрабатывает его (вы можете распечатать его или сделать что-то еще с ним), а затем он подталкивает правильную ветвь в стек для обработки, так как левая ветвь и сам узел выполнены.

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

У меня есть решение, которое использует только один в то время как цикл. Это похоже на решение Джованни, но, на мой взгляд, оно выглядит чище и читаемо. В частности, дизайн похож на рекурсивное решение для 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