本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如下:
先序遍历:
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); } } |
希望本文所述对大家C程序算法设计的学习有所帮助。