在网上看了一些用非递归实现先序中序后序遍历二叉树的代码，都很混乱，while、if各种组合嵌套使用，逻辑十分不清晰，把我也搞懵了。想了大半天，写了大半天，突然开了窍，实际上二叉树的这三种遍历在逻辑上是十分清晰的，所以才可以用递归实现的那么简洁。既然逻辑如此清晰，那么用非递归实现也应该是清晰的。
自认为自己的代码比网上搜到的那些都清晰得多，好理解得多。
稍微解释一下：
先序遍历。将根节点入栈，考察当前节点（即栈顶节点），先访问当前节点，然后将其出栈（已经访问过，不再需要保留），然后先将其右孩子入栈，再将其左孩子入栈（这个顺序是为了让左孩子位于右孩子上面，以便左孩子的访问先于右孩子；当然如果某个孩子为空，就不用入栈了）。如果栈非空就重复上述过程直到栈空为止，结束算法。
中序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过（有标记），则将其左孩子入栈，否则访问当前节点并将其出栈，再将右孩子入栈。如果栈非空就重复上述过程直到栈空为止，结束算法。
后序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过，则将其左孩子入栈，否则如果其右孩子未被访问过，则将其右孩子入栈，如果都已经访问过，则访问其自身，并将其出栈。如果栈非空就重复上述过程直到栈空为止，结束算法。
其实，这只不过是保证了先序中序后序三种遍历的定义。对于先序，保证任意一个节点先于其左右孩子被访问，还要保证其左孩子先于右孩子被访问。对于中序，保证任意一个节点，其左孩子先于它被访问，右孩子晚于它被访问。对于后序，保证任意一个节点的左孩子右孩子都先于它被访问，其中左孩子先于右孩子被访问。如是而已。
代码里应该体现得比较清楚。这里不光给出了非递归版本，也给出了递归版本。
#include <iostream>#include <stack> using namespace std; struct TreeNode { int data; TreeNode* left; TreeNode* right; int flag;}; typedef TreeNode *TreePtr; TreePtr CreateTree(){ TreePtr root = new TreeNode; cout<<"input the data :\n"; int n; cin>>n; if (n == -1) { return NULL; } else { root->data = n; root->flag = 0; root->left = CreateTree(); root->right = CreateTree(); } return root;} void PreOrderRecursion(TreePtr p){ if (p == NULL) { return; } cout<<p->data<<" "; PreOrderRecursion(p->left); PreOrderRecursion(p->right);} void InOrderRecursion(TreePtr p){ if (p == NULL) { return; } InOrderRecursion(p->left); cout<<p->data<<" "; InOrderRecursion(p->right);} void PostOrderRecursion(TreePtr p){ if (p == NULL) { return; } PostOrderRecursion(p->left); PostOrderRecursion(p->right); cout<<p->data<<" ";} void PreOrderNoRecursion(TreePtr p){ cout<<"PreOrderNoRecursion\n"; stack<TreeNode> stk; TreeNode t = *p; stk.push(t); while (!stk.empty()) { t = stk.top(); stk.pop(); cout<<t.data<<" "; if (t.right != NULL) { stk.push((*t.right)); } if (t.left != NULL) { stk.push((*t.left)); } }} void InOrderNoRecursion(TreePtr p){ cout<<"InOrderNoRecursion\n"; stack<TreeNode> stk; TreeNode t = *p; stk.push(t); while (!stk.empty()) { if (stk.top().flag == 0) { stk.top().flag++; if (stk.top().left != NULL) { stk.push(*(stk.top().left)); } } else { t = stk.top(); stk.pop(); cout<<t.data<<" "; if (t.right != NULL) { stk.push(*(t.right)); } } }} void PostOrderNoRecursion(TreePtr p){ cout<<"PostOrderNoRecursion\n"; stack<TreeNode> stk; TreeNode t = *p; stk.push(t); while (!stk.empty()) { if (stk.top().flag == 0) { stk.top().flag++; if (stk.top().left != NULL) { stk.push(*(stk.top().left)); } } else if (stk.top().flag == 1) { stk.top().flag++; if (stk.top().right != NULL) { stk.push(*(stk.top().right)); } } else { cout<<stk.top().data<<" "; stk.pop(); } }} int main(){ TreePtr t = CreateTree(); cout<<"PreOrderRecursion\n"; PreOrderRecursion(t); cout<<"\n"; cout<<"InOrderRecursion\n"; InOrderRecursion(t); cout<<"\n"; cout<<"PostOrderRecursion\n"; PostOrderRecursion(t); cout<<"\n"; PreOrderNoRecursion(t); cout<<"\n"; InOrderNoRecursion(t); cout<<"\n"; PostOrderNoRecursion(t); cout<<"\n";}
