非遞歸PostOrder使用並行堆棧的二叉樹遍歷

Question

我想採用非遞歸後序二叉樹遍歷的這種pseucode-ish算法，並將其實際實現爲代碼。本質上，我假設創建兩個並行堆棧，一個用於保存對節點的引用，另一個用於保存整數值1或2，以確定是否訪問了左側子樹或右側子樹。我根據他們給我的算法創建了算法，但由於某種原因，它只打印了一些數字，而沒有按照正確的順序排列，我覺得我把它理解爲它​​應該是的，但它現在正在工作，任何幫助都會很好。

繼承人他們要我做什麼：

1.create stack(s) 
2. current = root; 
3.v = 0; 
4. if (current is null) 
    the binary tree is empty 
5. if (current is not null) 
    a. push current onto stack; 
    b. push 1 onto stack; 
    c. current = current.lLink; 
6. while (stack is not empty) 
     if (current is not null and v is 0) 
     { 
      push current and 1 onto stack; 
      current = current.lLink 
     } 
     else 
     { 
      pop stack into current and v; 
      if (v == 1) 
      { 
       push current and 2 onto stack; 
       current = current.rLink; 
       v = 0; 
      } 
      else 
       visit current; 
     } 

這裏是我實現它：

public void nonRecursivePostTraversal() 
{ 
    LinkedStackClass<BinaryTreeNode<T> > stack 
    = new LinkedStackClass<BinaryTreeNode<T> >();//create stack 

    //create parallel stack of integers 
    LinkedStackClass<Integer> stackInt = new LinkedStackClass<Integer>(); 

    BinaryTreeNode<T> current; 
    current = root; 

    Integer v = 0; 

    if (current == null) 
     stack = null; 

    if (current != null) 
    { 
     stack.push(current); 
     v = 1; 
     stackInt.push(v); 
     current = current.lLink; 
    } 


    while (!stack.isEmptyStack()) 
     if (current != null && v == 0) 
     { 
      stack.push(current); 
      v = 1; 
      stackInt.push(v); 
      current = current.lLink; 

     } 
     else 
     { 
      current = (BinaryTreeNode<T>) stack.peek(); 
      stack.pop(); 
      v = (Integer) stackInt.peek(); 
      stackInt.pop(); 
      if (v == 1) 
      { 
       stack.push(current); 
       v = 2; 
       stackInt.push(v); 
       current = current.rLink; 
       v = 0; 
      } 
      else 
       System.out.print(current.info + " "); 
     } 

}//end alg 

Answer 1

public static void nonRecursivePostOrder(BinaryTreeNode root){ 


    Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>(); 
    List<BinaryTreeNode> returnNodes = new LinkedList<BinaryTreeNode>(); 


     while (true) { 
      if (root != null) { 

       if (returnNodes.contains(root)) { 
        returnNodes.add(stack.pop()); 
        root = null; 
       } else { 
        stack.push(root); 
        root = root.getLeft(); 
       } 

      } else { 
       if (stack.isEmpty()) { 
        break; 
       } else if (stack.peek().getRight() == null) { 
        root = stack.pop(); 
        returnNodes.add(root); 
        if (root == stack.peek().getRight()) { 
         returnNodes.add(stack.pop()); 
        } 
       } 

       if (!stack.isEmpty()) { 
        root = stack.peek().getRight(); 
       } else { 
        root = null; 
       } 
      } 
     } 

     for(BinaryTreeNode node : returnNodes) 
      System.out.print(node.getData()+" "); 

}