在学习二叉树遍历时，大家都很容易接受递归写法，好理解。对于非递归写法，基本思想是用栈消除递归，但是教材上的前序、中序和后序基本上三个写法，还很难理解。博主亲身经历，找工作中，考查二叉树遍历的非递归写法还是常见的。所以决心整理出此文，方便理解和记忆二叉树遍历。
来复习一下二叉树的递归遍历。
-
struct
TreeNode {
-
int
data;
-
TreeNode * left, * right;
-
};
-
-
void
preOrderTraverse(TreeNode * root,
void
(*visit)(TreeNode *)) {
-
if
(root) {
-
visit(root);
-
preOrderTraverse(root->left, visit);
-
preOrderTraverse(root->right, visit);
-
}
-
}
-
-
void
inOrderTraverse(TreeNode * root,
void
(*visit)(TreeNode *)) {
-
if
(root) {
-
inOrderTraverse(root->left, visit);
-
visit(root);
-
inOrderTraverse(root->right, visit);
-
}
-
}
-
-
void
postOrderTraverse(TreeNode * root,
void
(*visit)(TreeNode *)) {
-
if
(root) {
-
postOrderTraverse(root->left, visit);
-
postOrderTraverse(root->right, visit);
-
visit(root);
-
}
-
}
首先，博主找到了一篇类似论文，
《更简单的非递归遍历二叉树的方法》
，该文非常漂亮的将三种遍历方法统一起来，
除了有三行代码的顺序不一样外
。该实现中，对每个节点定义了一个pair对，通过改变局部入栈顺序实现整体遍历的不同。
本文意图使用常见的二叉树遍历的形式，简洁的实现这三种遍历。
void preOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root;
while(p != NULL || !s.empty()) {
while(p != NULL) {
visit(p);
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
p = p->right;
s.pop();
}
}
}
void inOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root;
while(p != NULL || !s.empty()) {
while(p != NULL) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
visit(p);
p = p->right;
s.pop();
}
}
}
void postOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root, *pre = NULL;
while(p != NULL || !s.empty()) {
while(p != NULL) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
if( p->right == NULL || p->right == pre) {
visit(p);
pre =
p;
p = NULL;
s.pop();
}
else {
p = p->right;
}
}
}
}
在前序遍历的代码中，最外层是while循环直到栈空且p为空，里面的while循环，不停访问根节点p，且迭代p=p->right，直到p为空。此时，从root开始的所有左分支的根节点均已被访问。到if分支时，取栈顶节点，切换到其右子树开始迭代。
前序遍历和中序遍历区别仅在于visit函数的调用位置不同
。
中序和后序的区别在于调用visit的时机不一致
。教材上的实现中，后序遍历需要一个标志来记录当前节点是否被访问过。在本文的实现中，通过一个pre指针记录被访问的最后一个元素，通过p->right==pre的比较来确认p是否被访问过。当然，直接访问p的另一情形是p没有右孩子。在这样的实现下，中序和后序的区别尽可能小。三种实现中，代码结构较一致，只有较少的变动。
希望本文可以方便那些学习非递归遍历二叉树的同学。
欢迎大家留言讨论！