数据结构考试前闲的蛋疼，整理课本。
结点建立
struct node { int v; struct node* left, *right; int flag; //后序遍历 }; node * root;
中序遍历
模拟深搜过程，在第一次回溯的时候输出，即为中序遍历
1 stack<node *> Q1; 2 node * pre = root; 3 while (1) 4 { 5 while (pre!=NULL) 6 { 7 Q1.push(pre); 8 pre = pre->left; 9 } 10 // 一直往左走 11 do 12 { 13 pre = Q1.top(); 14 cout << pre->v<<" ";Q1.pop(); 15 }while(pre->right==NULL&&!Q1.empty()); 16 // 回溯到能往左走 17 if (pre->right==NULL) break; 18 // 结束的条件是 回溯到 队列为空了，还没找到能往左走的结点 19 // PS:结束上述循环的两种情况，①队列为空 ②回溯到能走的结点 20 pre = pre->right; 21 } 22 cout << endl;
先序遍历
模拟深搜过程，在第一次加入栈的时候输出
1 //与中序遍历相当类似 2 stack<node *> Q3; 3 pre = root; 4 while (1) 5 { 6 while (pre!=NULL) 7 { 8 cout << pre->v<<" ";Q3.push(pre); 9 pre = pre->left; 10 } 11 do 12 { 13 pre = Q3.top(); 14 Q3.pop(); 15 }while(pre->right==NULL&&!Q3.empty()); 16 if (pre->right==NULL) break; 17 pre = pre->right; 18 } 19 cout << endl; 20 21 先序遍历非递归
后序遍历
和以上两个遍历的区别是
中序遍历和先序遍历，节点输出位置容易判断
先序是：在加入新节点之前
中序是：在加入右儿子之前或没有右儿子时
而对于后序遍历
没有右儿子或右儿子已经被遍历完成
中序遍历在第一次回溯之后，完全可以将根节点pop，这样就会避免重复访问，并且也已经输出了。但是对于后序遍历，是在第二遍回溯之后输出，所以不能pop。正因如此，回溯过程无法判断当前节点是第几次回溯，所以需要一个标志变量FLAG。
1 stack<node *> Q2; 2 pre = root; 3 while (1) 4 { 5 while (pre!=NULL) 6 { 7 Q2.push(pre); 8 pre = pre->left; 9 } 10 //一直往左走 11 while(!Q2.empty()&&(pre = Q2.top())&&(pre->right==NULL||pre->flag == 1)) 12 { 13 cout << pre->v<<" "; 14 Q2.pop(); 15 } 16 // 回溯到能往右走，不能往右走的原因有，没有右儿子，右结点已经被访问 17 // do-while 和 while 的区分！ 18 if (Q2.empty()) break; 19 // 搜索结束条件 20 pre->flag = 1; 21 pre = pre->right; 22 } 23 cout << endl;
原文：http://www.cnblogs.com/HITLJR/p/6241499.html
