после обхода порядка в двоичном дереве с использованием одного стека

Question

Я хочу сделать обратный ход двоичного дерева, используя только один стек. Это мой код, прежде всего я нажимаю левые элементы в стек до достижения нулевого значения. Затем я выталкиваю элемент и проверяю, является ли выпадающий элемент и правый элемент текущего верхнего стека одинаковым или нет. Но так или иначе это происходит в бесконечном цикле. можешь мне сказать почему??

public void postorderonestack(BinNode root) 
{ 
    BinStack s=new BinStack(); 

    while(true) 
    { 
     if(root!=null) 
     { 
      s.push(root); 
      root=root.getLeft(); 
     } 
     else 
     { 
      if(s.isEmpty()) 
      { 
       System.out.println("Stack is Empty"); 
       return; 
      } 

      else if(s.top().getRight()==null) 
      { 
       root=s.pop(); 
       System.out.println(root.getKey()); 

       if(root==s.top().getRight()) 
       { 
        System.out.print(s.top().getKey()); 
        s.pop(); 
       } 
      } 

      if(!s.isEmpty()) 
       root=s.top().getRight(); 

      else root=null; 
     } 
    } 
} 

Answer 1

Это код из моего ответа на другой вопрос (Post order traversal of binary tree without recursion). Он работает с одним стеком и не использует посещенный флаг.

private void postorder(Node head) { 
    if (head == null) { 
    return; 
    } 
    LinkedList<Node> stack = new LinkedList<Node>(); 
    stack.push(head); 

    while (!stack.isEmpty()) { 
    Node next = stack.peek(); 

    if (next.right == head || next.left == head || 
     (next.left == null && next.right == null)) { 
     stack.pop(); 
     System.out.println(next.value); 
     head = next; 
    } 
    else { 
     if (next.right != null) { 
     stack.push(next.right); 
     } 
     if (next.left != null) { 
     stack.push(next.left); 
     } 
    } 
    } 
} 

Answer 2

Там бесконечный цикл в этом коде позволяет рассматривать Направо перекошенное дерево illustarte это:

1 имеет правый ребенок 2

2 имеет право ребенка 3

3 является листовым узлом

В первые 3 петли 1, за которыми следуют 2, а затем 3, будут вставлены в стек. Теперь на четвертом цикле он входит в другую часть, теперь он печатает 3, а затем 2 и всплывает.

после заявления

else if(s.top().getRight()==null) 

Заявлении

if(!s.isEmpty()) 

будет толкать 2 снова на стеке. Это вызывает бесконечный цикл.

Код является ошибочным.

Заявление

if(root==s.top().getRight()) 

должен стать цикл в то время, чтобы решить эту проблему.

Answer 3

Почему бы не сделать это рекурсивно?

public void postorder(BinNode root) { 
    if (root == null) 
     return; 
    postorder(root.getLeft()); 
    postorder(root.getRight()); 
    System.out.println(root.getKey()); 
}