没有访问数组的迭代后序遍历

Question

我最近开始学习计算机科学和Java编码，并遇到了Traversal技术。我正在使用Stack编写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） 如果不为null，则将root.right写入堆栈 推根 root = root.left to stack 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推入Stack。
5. 现在你将9作为当前并将其推入Stack。
6. 现在你检查9的左边是null。
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