在網(wǎng)上看了一些用非遞歸實現(xiàn)先序中序后序遍歷二叉樹的代碼，都很混亂，while、if各種組合嵌套使用，邏輯十分不清晰，把我也搞懵了。想了大半天，寫了大半天，突然開了竅，實際上二叉樹的這三種遍歷在邏輯上是十分清晰的，所以才可以用遞歸實現(xiàn)的那么簡潔。既然邏輯如此清晰，那么用非遞歸實現(xiàn)也應(yīng)該是清晰的。
自認為自己的代碼比網(wǎng)上搜到的那些都清晰得多，好理解得多。
稍微解釋一下：
先序遍歷。將根節(jié)點入棧，考察當前節(jié)點（即棧頂節(jié)點），先訪問當前節(jié)點，然后將其出棧（已經(jīng)訪問過，不再需要保留），然后先將其右孩子入棧，再將其左孩子入棧（這個順序是為了讓左孩子位于右孩子上面，以便左孩子的訪問先于右孩子；當然如果某個孩子為空，就不用入棧了）。如果棧非空就重復上述過程直到?？諡橹梗Y(jié)束算法。
中序遍歷。將根節(jié)點入棧，考察當前節(jié)點（即棧頂節(jié)點），如果其左孩子未被訪問過（有標記），則將其左孩子入棧，否則訪問當前節(jié)點并將其出棧，再將右孩子入棧。如果棧非空就重復上述過程直到?？諡橹?，結(jié)束算法。
后序遍歷。將根節(jié)點入棧，考察當前節(jié)點（即棧頂節(jié)點），如果其左孩子未被訪問過，則將其左孩子入棧，否則如果其右孩子未被訪問過，則將其右孩子入棧，如果都已經(jīng)訪問過，則訪問其自身，并將其出棧。如果棧非空就重復上述過程直到?？諡橹?，結(jié)束算法。
其實，這只不過是保證了先序中序后序三種遍歷的定義。對于先序，保證任意一個節(jié)點先于其左右孩子被訪問，還要保證其左孩子先于右孩子被訪問。對于中序，保證任意一個節(jié)點，其左孩子先于它被訪問，右孩子晚于它被訪問。對于后序，保證任意一個節(jié)點的左孩子右孩子都先于它被訪問，其中左孩子先于右孩子被訪問。如是而已。
代碼里應(yīng)該體現(xiàn)得比較清楚。這里不光給出了非遞歸版本，也給出了遞歸版本。
#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"; }
