黑马程序员技术交流社区

标题: 关于二叉树的遍历问题 [打印本页]

---

作者: 唐秀启    时间: 2011-12-11 10:15
标题: 关于二叉树的遍历问题


本来想问问来。。刚刚找到了数据结构课本看了看以前的总结，感觉挺有用的，与大家分享下吧


二叉树的遍历
先序遍历（先根遍历）
  （1）访问根结点 （2）先序遍历左子树（3）先序遍历右子树
中序遍历
  （1）中序遍历左子树（2）访问跟结点（3）中序遍历右子树
后序遍历（后根遍历）
  （1）后序遍历左子树（2）后序遍历右子树（3）访问根结点。
非递归后序遍历算法

1. public void Postorder_(BinTreeNode t) {   
   
2.      Stack<BinTreeNode> stack = new Stack<BinTreeNode>();   
   
3.      BinTreeNode pre = t;   
   
4.      if (t != null) {   
   
5.          while (true) {   
   
6.              if (t.right != pre && t.left != pre && t.left != null) {   
   
7.                  stack.push(t);   
   
8.                  pre = t;   
   
9.                  t = t.left;   
   
10.              } else if (t.right != pre && t.right != null) {   
    
11.                  stack.push(t);   
    
12.                  pre = t;   
    
13.                  t = t.right;   
    
14.              } else {   
    
15.                  System.out.println(t.data);   
    
16.                  pre = t;   
    
17.                  if (!stack.isEmpty()) {   
    
18.                      t = stack.pop();   
    
19.                  } else {   
    
20.                      break;   
    
21.                  }   
    
22.              }   
    
23.          }   
    
24.      }   
    
25. }
    

复制代码

---

作者: 小春同学    时间: 2011-12-11 10:29


{:soso_e132:}，谢谢楼主分享，以下个人愚见：
TreeSet采用后序遍历——>是值插入存储的时候；但输出的时候要看具体自定义的比较器的方法了，默认输出应该是中序遍历，

---

作者: 唐秀启    时间: 2011-12-11 11:09

熊明春 发表于 2011-12-11 10:29
，谢谢楼主分享，以下个人愚见：
TreeSet采用后序遍历——>是值插入存储的时候；但输出的时 ...

不是啊  存储是按二叉树存储，你都说遍历了，而遍历的意思就是访问。

我还是认为TreeSet采用的是后序遍历。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2