java - 非递归后序遍历代码,请问bug出在哪里?
巴扎黑
巴扎黑 2017-04-17 13:17:35
0
2
386
javapublic 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)
请问代码哪里出错了?

巴扎黑
巴扎黑

membalas semua (2)
PHPzhong

按你的用例 在纸上走了一遍, 逻辑应该没有错. 有一个bug:

在node 14 处理后, 栈里只有 10 一个元素了,currentnull; 接着一个循环,

current = stack.pop();

为10, 栈为空.
所以下面的code应该是:

if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek() ){

    Ty80

    见正确回复

      Muat turun terkini
      Lagi>
      kesan web
      Kod sumber laman web
      Bahan laman web
      Templat hujung hadapan
      Tentang kita Penafian Sitemap
      Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!