Итеративный обход пост-заказа без посещенного массива

Question

Я недавно начал изучать информатику и программирование на Java и познакомился с методами Traversal. Я пишу код Java с использованием стека. Я был с этой проблемой и не мог найти никакого решения. Есть ли в любом случае, мы можем реализовать обход Post Order, используя только один стек (без какой-либо дополнительной структуры данных или дополнительного пространства)?

Я пытался это сделать, и вот мой код.

class node {
int data;
node left, right;
node(int val){
    data = val;
    left = right = null;
}
}
 public class binaryt {

public static void postorder(node root) {
    node current = root;
    Stack<node> st = new Stack<>();
    System.out.println();
    System.out.print("Post-order : ");  
    while(current!=null) {
        st.push(current);
        current = current.left;
    }
    while(!st.empty()) {
        current = st.pop();
        if(current.right==null) {
            System.out.print(current.data+" ");
            current = null;
        }
        else {
            st.push(current);
            current = current.right;
            while(current!=null) {
                st.push(current);
                current = current.left;
            }
        }
    }
}
public static void main(String[] args) {
    node root=null;


    root = new node(12);
    root.left = new node(8);
    root.left.left = new node(2);
    root.left.right = new node(9);
    root.right= new node(16);
    root.right.left= new node(13);
    root.right.right= new node(18);

    postorder(root);
}

}

Я не могу найти, что не так с кодом, так как он работает в бесконечном цикле. Если бы кто-нибудь мог мне помочь, это было бы огромной милостью. Большое вам спасибо.

Answer 1

Лучший способ выучить эти надоедливые алгоритмы - это немного потерпеть и найти свое собственное решение, которое застрянет в вашем мозгу - так что вы поступаете правильно. Это всегда тяжело для меня.

• сделать

  • while (root! = Null)

    • вставить root.right в стек, если не ноль
    • push root
    • root = root.left в стек

  • root = stack.pop ()

  • if (root.right == stack.peek)
    • stack.pop ()
    • толкнуть корень в стек
    • root = root.right
  • еще
    • печать корня
    • root = null;

• пока стек! пусто

Ваша проблема

Итак, вероятно, есть несколько общих вещей не так в вашей попытке. Но вот тот, который я сначала исправлю, а потом, думаю, вы сможете получить другие:

• Вы не можете просто пойти налево вниз по всему дереву, чтобы начать с. Вам нужно идти влево только после того, как вы проверите правый узел и добавите его в стек. Помните, что рекурсивная реализация уже имела бы корневой / текущий фрейм, тогда она вызывала бы левое и правое деревья. Таким образом, это означает, что текущий кадр идет последним после завершения левого и правого вызовов. Таким образом, стек вызовов функций логически содержит левое поддерево, затем правое поддерево, а затем текущий кадр.

Answer 2

Это то, что происходит в вашем коде:

1. сначала вы нажимаете 12,8 и 2 в стеке

2. Тогда для 2 нет левого ребенка, поэтому вы приходите к while

3. сейчас 2 выдан, и у него нет правого потомка, поэтому теперь два значения в стеке 8,12

4. Далее идет 8 у него есть правильный ребенок, вы снова толкаете 8 в стек.

5. Теперь вы берете 9 в качестве тока и помещаете его в стек.

6. Теперь вы проверяете слева от 9 , который равен нулю.

7. так что вы снова начинаете с цикла while(!st.empty()) {, который имеет элементы 9, 8,12

8. опять то же самое повторяется, и ваш цикл while никогда не заканчивается

вы также можете увидеть на консоли : Пост-заказ: 2 9 9 9 9 ..... Продолжение

Так вот в чем проблема.

Ниже приведено решение:

public static void postorderIter( node root) {
    if( root == null ) return;

    Stack<node> s = new Stack<node>( );
    node current = root;

    while( true ) {

        if( current != null ) {
            if( current.right != null ) 
                s.push( current.right );
            s.push( current );
            current = current.left;
            continue;
        }

        if( s.isEmpty( ) ) 
            return;
        current = s.pop( );

        if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
            s.pop( );
            s.push( current );
            current = current.right;
        } else {
            System.out.print( current.data + " " );
            current = null;
        }
    }
}

Answer 3

Вот пример, который использует рекурсию, чтобы сделать ее более читабельной.

public static void postorder(node root) {
    Stack<node> nodes = new Stack<>();
    node curr = root;

    postOrderRecursive(curr, nodes);

    int size = nodes.size();
    while(size > 0){

        System.out.println(nodes.elementAt(0).data);
        nodes.remove(0);
        size = nodes.size();
    }
}
private static void postOrderRecursive(node n, Stack<node> nodes){
    if(n.left != null)
        postOrderRecursive(n.left, nodes);
    if(n.right != null)
        postOrderRecursive(n.right, nodes);

    nodes.push(n);
}

Вывод с учетом вашей инициализации: 2 9 8 13 18 16 12