Binary Tree Traversal Algorithms (二叉树遍历算法)

本文共列出了11个常见的二叉树遍历算法。二叉树的遍历主要有深度优先遍历和广度优先遍历。深度优先遍历包含前序遍历、中序遍历和后序遍历。

值得一提的是，其中的 Morris 算法可以线性时间不需要额外空间（用户栈或系统栈空间）实现二叉树的前序遍历、中序遍历和后序遍历。关于Morris算法，可参考 http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html

算法清单：

　　A1、 A2、 A3，分别是中序遍历的递归、迭代、和Morris算法实现。

　　A4、 A5、 A6，分别是前序遍历的递归、迭代、和Morris算法实现。

　　A7、 A8、 A9，分别是后序遍历的递归、迭代、和Morris算法实现。

　　A10 是广度优先遍历算法实现。

　　A11 ZigZag顺序的遍历算法。

C++源代码：

  1 #include <iostream>
  2 #include <stack>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct bt_node {
  7     int value;
  8     bt_node *left, *right;
  9     bt_node(int val = 0) 
 10         : value(val), left(NULL), right(NULL) {} 
 11 };
 12 
 13 void process(bt_node* pnode) {
 14     if (pnode != NULL) 
 15         cout << pnode->value << " ";
 16 }
 17 
 18 // A1
 19 void recursive_inorder_traversal(bt_node* root) {
 20     if (root != NULL) {
 21         recursive_inorder_traversal(root->left);
 22         process(root);
 23         recursive_inorder_traversal(root->right);
 24     }
 25 }
 26 
 27 // A2
 28 void iterative_inorder_traversal(bt_node* root) {
 29     stack<bt_node*> _stack;
 30     bt_node* p = root;
 31     while (p != NULL) {
 32         while (p != NULL) {
 33             _stack.push(p);
 34             p = p->left;
 35         }
 36         p = _stack.top();
 37         _stack.pop();
 38         process(p);
 39         while (p->right == NULL && !_stack.empty()) {
 40             p = _stack.top();
 41             _stack.pop();
 42             process(p);
 43         }
 44         p = p->right;
 45     }
 46 }
 47 
 48 // A3 
 49 void morris_inorder_traversal(bt_node* root) {
 50     bt_node* p = root;
 51     while (p != NULL) {
 52         if (p->left == NULL) {
 53             process(p);
 54             p = p->right;
 55         } else {
 56             bt_node* tmp = p->left;
 57             while (tmp->right != NULL && tmp->right != p) {
 58                 tmp = tmp->right;
 59             }
 60             if (tmp->right == NULL) {
 61                 tmp->right = p;
 62                 p = p->left;
 63             } else {
 64                 tmp->right = NULL;
 65                 process(p);
 66                 p = p->right;
 67             }
 68         }
 69     }
 70 }
 71 
 72 // A4
 73 void recursive_preorder_traversal(bt_node* root) {
 74     if (root != NULL) {
 75         process(root);
 76         recursive_preorder_traversal(root->left);
 77         recursive_preorder_traversal(root->right);
 78     }
 79 }
 80 
 81 // A5
 82 void iterative_preorder_traversal(bt_node* root) {
 83     stack<bt_node*> _stack;
 84     bt_node* p = root;
 85     while (p != NULL) {
 86         while (p != NULL) {
 87             process(p);
 88             _stack.push(p);
 89             p = p->left;
 90         }
 91         p = _stack.top();
 92         _stack.pop();
 93         while (p->right == NULL && !_stack.empty()) {
 94             p = _stack.top();
 95             _stack.pop();
 96         }
 97         p = p->right;
 98     }
 99 }
100 
101 // A6
102 void morris_preorder_traversal(bt_node* root) {
103     bt_node* p = root;
104     while (p != NULL) {
105         if (p->left == NULL) {
106             process(p);
107             p = p->right;
108         } else {
109             bt_node* tmp = p->left;
110             while (tmp->right != NULL && tmp->right != p) 
111                 tmp = tmp->right;
112             if (tmp->right == NULL) {
113                 tmp->right = p;
114                 process(p);
115                 p = p->left;
116             } else {
117                 tmp->right = NULL;
118                 p = p->right;
119             }
120         }
121     }
122 }
123 
124 
125 // A7
126 void recursive_postorder_traversal(bt_node* root) {
127     if (root != NULL) {
128         recursive_postorder_traversal(root->left);
129         recursive_postorder_traversal(root->right);
130         process(root);
131     }
132 }
133 
134 // A8
135 void iterative_postorder_traversal(bt_node* root) {
136     stack<bt_node*> _stack;
137     bt_node *p = root, *q = NULL;
138     while (p != NULL) {
139         _stack.push(p);
140         p = p->left;
141     }
142     while (!_stack.empty()) {
143         p = _stack.top();
144         if (p->right == NULL || p->right == q) {
145             _stack.pop();
146             process(p);
147             q = p;
148         } else {
149             p = p->right;
150             while (p != NULL) {
151                 _stack.push(p);
152                 p = p->left;
153             }
154         }
155     }
156 }
157 
158 bt_node* reverse(bt_node* pnode) {
159     bt_node aux_node;
160     bt_node* p = &aux_node;
161     bt_node* q = pnode;
162     while (q != NULL) {
163         bt_node* next = q->right;
164         q->right = p->right;
165         p->right = q;
166         q = next;
167     }
168     return p->right;
169 }
170 
171 void process_in_reverse_order(bt_node* pnode) {
172     pnode = reverse(pnode);
173     bt_node* p = pnode;
174     while (p != NULL) {
175         process(p);
176         p = p->right;
177     }
178     reverse(pnode);
179 }
180 
181 // A9
182 void morris_postorder_traversal(bt_node* root) {
183     bt_node dummy;
184     dummy.left = root;
185     bt_node *p = &dummy;
186     while (p != NULL) {
187         if (p->left == NULL) {
188             p = p->right;
189         } else {
190             bt_node* tmp = p->left;
191             while (tmp->right != NULL && tmp->right != p) 
192                 tmp = tmp->right;
193             if (tmp->right == NULL) {
194                 tmp->right = p;
195                 p = p->left;
196             } else {
197                 tmp->right = NULL;
198                 process_in_reverse_order(p->left);
199                 p = p->right;
200             }
201         }
202     }
203 }
204 
205 // A10
206 void breadth_first_traversal(bt_node* root) {
207     queue<bt_node*> _queue;
208     _queue.push(root);
209     while (!_queue.empty()) {
210         bt_node* p = _queue.front();
211         _queue.pop();
212         process(p);
213         if (p->left != NULL) {
214             _queue.push(p->left);
215         } 
216         if (p->right != NULL) {
217             _queue.push(p->right);
218         }
219     }
220 }
221 
222 // A11
223 void zigzag_order_traversal(bt_node* root) {
224     stack<bt_node*> _stack1;
225     stack<bt_node*> _stack2;
226     _stack1.push(root);
227     int left_first = 1;
228     while (!_stack1.empty()) {
229         while (!_stack1.empty()) {
230             bt_node* p = _stack1.top();
231             _stack1.pop();
232             process(p);
233             if (left_first) {
234                 if (p->left != NULL)
235                     _stack2.push(p->left);
236                 if (p->right != NULL) 
237                     _stack2.push(p->right);
238             } else {
239                 if (p->right != NULL)
240                     _stack2.push(p->right);
241                 if (p->left != NULL)
242                     _stack2.push(p->left);
243             }
244         }
245         left_first = left_first ^ 0x01;
246         _stack1.swap(_stack2); // C++11 Standard
247     }
248 }
249 
250 // Test
251 int main() {
252     const int n = 7;
253     bt_node* ptr[n];
254     for (int i = 0; i < n; i++) {
255         ptr[i] = new bt_node(i+1);
256     }
257     ptr[0]->left = ptr[1];
258     ptr[0]->right = ptr[2];
259     ptr[1]->left = ptr[3];
260     ptr[1]->right = ptr[4];
261     ptr[2]->left = ptr[5];
262     ptr[4]->left = ptr[6];
263 
264     /*
265      *             1
266      *           /   
267      *          2     3
268      *         /    /
269      *        4   5 6 
270      *           /
271      *          7
272      */
273 
274     recursive_inorder_traversal(ptr[0]);
275     cout << endl;
276     iterative_inorder_traversal(ptr[0]);
277     cout << endl;
278     morris_inorder_traversal(ptr[0]);
279     cout << endl;
280 
281     recursive_preorder_traversal(ptr[0]);
282     cout << endl;
283     iterative_preorder_traversal(ptr[0]);
284     cout << endl;
285     morris_preorder_traversal(ptr[0]);
286     cout << endl;
287 
288     recursive_postorder_traversal(ptr[0]);
289     cout << endl;
290     iterative_postorder_traversal(ptr[0]);
291     cout << endl;
292     morris_postorder_traversal(ptr[0]);
293     cout << endl;
294 
295     breadth_first_traversal(ptr[0]);
296     cout << endl;
297     zigzag_order_traversal(ptr[0]);
298     cout << endl;
299 
300     for (int i = 0; i < n; i++) {
301         delete ptr[i];
302     }
303     return 0;
304 }

程序输出：

4 2 7 5 1 6 3 
4 2 7 5 1 6 3 
4 2 7 5 1 6 3 
1 2 4 5 7 3 6 
1 2 4 5 7 3 6 
1 2 4 5 7 3 6 
4 7 5 2 6 3 1 
4 7 5 2 6 3 1 
4 7 5 2 6 3 1 
1 2 3 4 5 6 7 
1 3 2 4 5 6 7