本文以實(shí)例形式講述了C語言實(shí)現(xiàn)二叉樹的非遞歸遍歷方法。是數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)中常用的技巧。分享給大家供大家參考。具體方法如下：
先序遍歷：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void preOrder(Node *p) //非遞歸{ if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.push(t->right); if(t->left) s.push(t->left); }} |
中序遍歷：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void inOrder(Node *p){if(!p)return;stack< pair<Node*,int> > s;Node *t;int unUsed;s.push(make_pair(p,1));while(!s.empty()){t=s.top().first;unUsed = s.top().second;s.pop();if(unUsed){if(t->right)s.push( make_pair(t->right,1) );s.push( make_pair(t,0) );if(t->left)s.push( make_pair(t->left,1));}else printf("%d\n",t->data);}} |
后序遍歷：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void postOrder(Node *p){ if(!p) return; stack<pair<Node*,int> > s; Node *t; int unUsed; s.push(make_pair(p,1)); while(!s.empty()) { t=s.top().first; unUsed=s.top().second; s.pop(); if(unUsed) { s.push(make_pair(t,0); if(t->right) s.push(make_pair(t->right,1)); if(t->left) s.push(make_pair(t->left,1)); } else printf("%d\n",t->data); }} |
希望本文所述對(duì)大家C程序算法設(shè)計(jì)的學(xué)習(xí)有所幫助。
