二叉树的后序遍历
2015年10月20日, 发表于 长春
如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)
在学习数据结构的过程中，二叉树的遍历是必学的，而二叉树的非递归遍历又是其中的难点之一，我在查阅书籍和浏览blog的时候，看见的方法往往是在结点上加一个标志位作为辅助，以判断根结点的左右子树是否均遍历过，而且过程比较繁琐。
利用双栈来实现后根遍历
现在我们换一种思路，当我们用递归实现后序遍历的时候，是很简单的:
1 2 3 4 5 6 7 | void PostOrder(BiTreeNode *t){ if(t ==NULL) return; PostOrder(t->left); PostOrder(t->right); visit(t); } |
访问左子树->右子树->根，简单明了。 如果非递归后序遍历也采用这种思想，访问某个结点时，它的左右子树一定均访问过，那么就不需要标志位了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | //二叉树后根遍历 void PostOrder(BiTreeNode * t){ stack S1,S2; if (t ==NULL) return; S1.push(t); while(!S1.isEmpty()){ t=S1.pop(); S2.push(t); if(t->left!=NULL) S1.push(t->left); if(t->right!=NULL) S1.push(t->right); } while(!S2.isEmpty()){ t=S2.pop(); visit(t); } } |
这里用栈来模拟递归。