//這不是最有效的方法，但使用了標記為容易理解，記下

/* * description:樹的遍歷示例，非遞歸版本 * 入棧順序： * 前序： 右子樹 - 左子樹 - 當前節點 * 中序： 右子樹 - 當前節點 - 左子樹 * 后序： 當前節點 - 右子樹 - 左子樹 * * writeby: nick * date: 2012-10-22 23:56 */ #include <iostream> #include <stack>using namespace std;struct node {int item;bool flag;node *l, *r;node(int n){item=n; l=0; r=0; flag=false;} }; typedef node *link;//前序遍歷 void pretraverse(link h, void visit(link)) {stack<link> s;s.push(h);while(!s.empty()){h = s.top();s.pop();visit( h );if (h->r != 0) s.push(h->r);if (h->l != 0) s.push(h->l);} }//中序遍歷 void midtraverse(link h, void visit(link)) {stack<link> s;s.push(h);while(!s.empty()){h = s.top();s.pop();if(h->flag == true) {visit(h); continue;}if(h->r != 0 && h->r->flag == false) s.push(h->r);if(h->flag==false){ h->flag=true; s.push(h);}if(h->l != 0 && h->l->flag == false) s.push(h->l);}}//后序遍歷 void posttraverse(link h, void visit(link)) {stack<link> s;s.push(h);while(!s.empty()){h = s.top();s.pop();if(h->flag == true) {visit(h); continue;}if(h->flag==false){ h->flag=true; s.push(h);}if(h->r != 0 && h->r->flag == false) s.push(h->r);if(h->l != 0 && h->l->flag == false) s.push(h->l);} }void visit(link p) {cout << p->item << " "; }int main() {link root = new node(4);root->l = new node(5);root->r = new node(6);root->l->l = new node(7);root->l->r = new node(8);cout << "先序遍歷：";pretraverse(root, visit);cout << endl << "中序遍歷：";midtraverse(root, visit);root->flag = false;root->l->flag = false;root->r->flag = false;root->l->l->flag = false;root->l->r->flag = false;cout << endl << "后序遍歷：";posttraverse(root, visit);return 0; }

轉載于:https://www.cnblogs.com/wouldguan/archive/2012/10/23/2735511.html

總結

以上是生活随笔為你收集整理的C++遍历树-非递归递归-使用了标记位的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。