java
public static void postOrderNonrecur(Treenode rootnode){ if(rootnode==null){ return; } Stack
stack = new Stack (); Treenode current = rootnode; while(current !=null || stack.isEmpty()!=true){ //step 1 while(current!=null){ if(current.rightchild!=null){ stack.push(current.rightchild); } stack.push(current); current = current.leftchild; } current = stack.pop(); if(current.rightchild!=null && current.rightchild == stack.peek() ){ System.out.println("here"); stack.pop(); //出栈右孩子 stack.push(current); current = current.rightchild; } else{ System.out.println(current.value); current = null; } } }
测试用例是
出错是:
Exception in thread "main" 4
7
8
6
12
16
14
java.util.EmptyStackException
at java.util.Stack.peek(Unknown Source)
at gsm.Tree.postOrderNonrecur(Tree.java:110)
at gsm.Tree.main(Tree.java:140)
请问代码哪里出错了?
按你的用例 在纸上走了一遍, 逻辑应该没有错. 有一个bug:
在node 14 处理后, 栈里只有 10 一个元素了,
current
为null
; 接着一个循环,current = stack.pop();
为10, 栈为空.
所以下面的code应该是:
if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek() ){
见正确回复