本帖最后由 benbenqi 于 2011-12-11 10:17 编辑
本来想问问来。。刚刚找到了数据结构课本看了看以前的总结,感觉挺有用的,与大家分享下吧
二叉树的遍历
先序遍历(先根遍历)
(1)访问根结点 (2)先序遍历左子树(3)先序遍历右子树
中序遍历
(1)中序遍历左子树(2)访问跟结点(3)中序遍历右子树
后序遍历(后根遍历)
(1)后序遍历左子树(2)后序遍历右子树(3)访问根结点。
非递归后序遍历算法- public void Postorder_(BinTreeNode t) {
- Stack<BinTreeNode> stack = new Stack<BinTreeNode>();
- BinTreeNode pre = t;
- if (t != null) {
- while (true) {
- if (t.right != pre && t.left != pre && t.left != null) {
- stack.push(t);
- pre = t;
- t = t.left;
- } else if (t.right != pre && t.right != null) {
- stack.push(t);
- pre = t;
- t = t.right;
- } else {
- System.out.println(t.data);
- pre = t;
- if (!stack.isEmpty()) {
- t = stack.pop();
- } else {
- break;
- }
- }
- }
- }
- }
-
复制代码 |