本文实例讲述了C语言实现二叉树遍历的迭代算法，是数据结构算法中非常经典的一类算法。分享给大家供大家参考。
具体实现方法如下：
二叉树中序遍历的迭代算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
#include <iostream>#include <stack>using namespace std;struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* left; Node* right; }; Node* construct() { Node* node6 = new Node(16); Node* node5 = new Node(12); Node* node4 = new Node(8); Node* node3 = new Node(4); Node* node2 = new Node(14, node5, node6); Node* node1 = new Node(6, node3, node4); Node* node0 = new Node(10, node1, node2); return node0; }//递归算法void inorder(Node *root){ if (root == NULL) return; inorder(root->left); cout << root->item << " "; inorder(root->right);}void preorder(Node *root){ if(root == NULL) return; cout << root->item << " "; preorder(root->left); preorder(root->right);}void postorder(Node *root){ if (root == NULL) return; postorder(root->left); postorder(root->right); cout << root->item << " ";}void postorder2(Node *root){ if (root == NULL) return; stack<Node *> nstack; Node *pre = NULL; nstack.push(root); Node *node = NULL; while (!nstack.empty()) { node = nstack.top(); if (pre != node->left && pre != node->right) { if (node->right) nstack.push(node->right); if (node->left) nstack.push(node->left); } if (node->left == NULL && node->right == NULL || pre == node->left || pre == node->right) { cout << node->item << " "; nstack.pop(); } pre = node; }}void preorder2(Node *root){ if(root == NULL) return; stack<Node *> nstack; Node *node = root; while (node != NULL || !nstack.empty()) { while(node != NULL) { cout << node->item << " "; nstack.push(node); node = node->left; } node = nstack.top(); nstack.pop(); node = node->right; }}void preorder3(Node *root){ if (root == NULL) return; stack<Node *> nstack; nstack.push(root); Node *node = NULL; while (!nstack.empty()) { node = nstack.top(); nstack.pop(); cout << node->item << " "; if (node->right) nstack.push(node->right); if (node->left) nstack.push(node->left); }}//迭代算法void inorder2(Node *root){ if(root == NULL) return; stack<Node *> nstack; nstack.push(root); Node *next = root->left; while (next != NULL || !nstack.empty()) { while (next != NULL) { nstack.push(next); next = next->left; } next = nstack.top(); nstack.pop(); cout << next->item << " "; next = next->right; }}int main(){ Node *root = construct(); cout << "---------中序遍历递归---------" << endl; inorder(root); cout << endl; cout << "---------中序遍历迭代---------" << endl; inorder2(root); cout << endl; cout << "---------先序遍历递归---------" << endl; preorder(root); cout << endl; cout << "---------先序遍历迭代1---------" << endl; preorder2(root); cout << endl; cout << "---------先序遍历迭代2---------" << endl; preorder3(root); cout << endl; cout << "---------后序遍历递归---------" << endl; postorder(root); cout << endl; cout << "---------后序遍历迭代---------" << endl; postorder2(root);} |
关于前序遍历，后来又写的算法如下，供大家参考：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void preOrderIterator(Node *root){ if (root == NULL) return; stack<Node*> nstack; nstack.push(root); while (!nstack.empty()) { Node *top = nstack.top(); while (top != NULL) { if (top->left) nstack.push(top->left); cout << top->data << " "; top = top->left; } while (top == NULL && !nstack.empty()) { top = nstack.top()->right; nstack.pop(); } if (top != NULL) nstack.push(top); }} |
相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。
