二叉树的遍历(递归，迭代，Morris遍历）

二叉树的遍历：

先序，中序，后序；

二叉树的遍历有三种常见的方法，

最简单的实现就是递归调用，

另外就是飞递归的迭代调用，

最后还有O(1)空间的morris遍历；

二叉树的结构定义：

1 struct TreeNode {
2      int val;
3      TreeNode *left;
4      TreeNode *right;
5      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6  };

1.先序遍历：

递归：

1 void preOrderRecursive(TreeNode *root) {
2     if (!root)
3         return;
4     cout << root->val << " ";
5     preOrderRecursive(root->left);
6     preOrderRecursive(root->right);
7 }

迭代：

迭代要用到栈来保存父亲结点，

先序遍历，所有访问过的结点都先输出，

先遍历当前结点和当前结点的左子树，一直到左子树的最左边的结点，

遍历过的这些结点都入栈，左孩子为空时，栈顶元素设为当前结点，出栈，

然后把当前结点设为该节点的右孩子，循环一直到当前结点为空且栈也为空。

 1 void preOrderIterative(TreeNode *root) {
 2     if (!root)
 3         return;
 4     stack<TreeNode*> stk;
 5     TreeNode *cur = root;
 6     while (cur || !stk.empty()) {
 7         while (cur) {
 8             cout << cur->val << " ";
 9             stk.push(cur);
10             cur = cur->left;
11         }
12         if (!stk.empty()) {
13             cur = stk.top();
14             stk.pop();
15             cur = cur->right;
16         }
17     }
18 }
19 /* 
20  * 模拟递归
21  * */
22 void preOrderIterative1(TreeNode *root) {
23     if (!root)
24         return;
25     stack<TreeNode*> stk;
26     stk.push(root);
27     while (!stk.empty()) {
28         TreeNode* tp = stk.top();
29         stk.pop();
30         cout << tp->val << " ";
31         if (tp->right) 
32             stk.push(tp->right);
33         if (tp->left)
34             stk.push(tp->left);
35     }
36 }

Morris方法：

1.当前结点的左孩子为空，输出当前结点，并设置当前结点的右孩子为当前结点；

2.当前结点的左孩子不为空：

　　a.找到当前结点中序遍历的前驱结点，即为该节点的左孩子的最右边的结点，前驱结点的右孩子为空，则设置前驱结点的右孩子为当前结点，并输出当前结点，设当前结点的左孩子为当前结点；

　　b.前驱结点的右孩子为当前结点，则恢复前驱结点的右孩子为NULL，设当前结点的右孩子为当前结点；

 1 void preOrderMorris(TreeNode *root) {
 2     if (!root)
 3         return;
 4     TreeNode* cur = root;
 5     TreeNode* pre = NULL;
 6     while (cur) {
 7         if (cur->left == NULL) {
 8             cout << cur->val << " ";
 9             cur = cur->right;
10         }
11         else {
12             pre = cur->left;
13             while (pre->right != NULL && pre->right != cur) 
14                 pre = pre->right;
15             if (pre->right == NULL) {
16                 cout << cur->val << " ";
17                 pre->right = cur;
18                 cur = cur->left;
19             }
20             else {
21                 pre->right = NULL;
22                 cur = cur->right;
23             }
24         }
25     }
26 }

2.中序遍历：

递归：

1 void inOrderRecursive(TreeNode *root) {
2     if (!root)
3         return;
4     inOrderRecursive(root->left);
5     cout << root->val << " ";
6     inOrderRecursive(root->right);
7 }

迭代：

1.如果当前结点的左孩子不为空，则把当前结点的左孩子入栈，知道当前结点的左孩子为空；

2.如果栈不为空，则出栈，栈顶元素为当前结点，输出当前结点，并把当前结点的右孩子设为当前结点；

重复1，2直到当前结点为NULL且栈也为空；

 1 void inOrderIterative(TreeNode *root) {
 2     if (!root)
 3         return;
 4     stack<TreeNode*> stk;
 5     TreeNode *cur = root;
 6     while (cur || !stk.empty()) {
 7         while (cur) {
 8             stk.push(cur);
 9             cur = cur->left;
10         }
11         if (!stk.empty()) {
12             cur = stk.top();
13             stk.pop();
14             cout << cur->val << " ";
15             cur = cur->right;
16         }
17     }
18 }

Morris方法：

和先序遍历的过程类似，只不过输出结点的位置不一样，中序遍历是在2.b中，也就是前驱结点的右孩子为当前结点时，即当前结点的左子树都已经遍历完成时，输出当前结点；

 1 void inOrderMorris(TreeNode *root) {
 2     if (!root)
 3         return;
 4     TreeNode* cur = root;
 5     TreeNode* pre = NULL;
 6     while (cur) {
 7         if (cur->left == NULL) {
 8             cout << cur->val << " ";
 9             cur = cur->right;
10         }
11         else {
12             pre = cur->left;
13             while (pre->right != NULL && pre->right != cur)
14                 pre = pre->right;
15             if (pre->right == NULL) {
16                 pre->right = cur;
17                 cur = cur->left;
18             }
19             else {
20                 cout << cur->val << " ";
21                 pre->right = NULL;
22                 cur = cur->right;
23             }
24         }
25     }
26 }

3.后序遍历：

递归：

1 void postOrderRecursive(TreeNode *root) {
2     if (!root)
3         return;
4     postOrderRecursive(root->left);
5     postOrderRecursive(root->right);
6     cout << root->val << " ";
7 }

迭代：

后序遍历比先序、中序都要复杂，

第一种迭代方法，可以用两个栈来模拟递归的遍历；

栈1初始化时把根节点入栈，

1.栈1出栈，把出栈的元素加入栈2，然后把该元素的左孩子（如果不为空），右孩子（如果不为空）加入栈1，知道栈1为空；

2.栈2出栈直到空，每次出栈时输出栈顶元素；

通过两个栈，保证了栈2中的元素顺序，

第二种迭代方法，

用一个结点保存访问过的最后一个结点pre，如果pre为栈顶元素的右孩子，则说明栈顶元素的右子树已经遍历过了，直接输出栈顶元素，并把当前结点设为NULL，并更新pre为出栈的元素；

1.如果当前结点存在，则一直向左遍历，入栈遍历的元素，直到结点为空；

2.栈不为空时，出栈，当前结点为栈顶元素，

如果当前结点的右孩子不为空且不为pre，说明当前结点的右子树没有遍历过，设置当前结点为该节点的右孩子，

如果右孩子为空或者为pre，直接输出当前结点，更新pre为当前结点，并设当前结点为NULL，

重复1，2直到当前结点为NULL并且栈为空；

 1 void postOrderIterative(TreeNode *root) {
 2     if (!root) 
 3         return;
 4     stack<TreeNode*> stk;
 5     TreeNode *cur = root;
 6     TreeNode *pre = NULL;
 7     while (cur || !stk.empty()) {
 8         while (cur) {
 9             stk.push(cur);
10             cur = cur->left;
11         }
12         if (!stk.empty()) {
13             cur = stk.top();
14             if (cur->right != NULL && cur->right != pre) {
15                 cur = cur->right;
16             }
17             else {
18                 cout << cur->val << " ";
19                 pre = cur;
20                 stk.pop();
21                 cur = NULL;
22             }
23         }
24     }
25 }
26 /*
27  * 双栈法
28  */
29 void postOrderIterative1(TreeNode *root) {
30     if (!root) 
31         return;
32     stack<TreeNode*> stk1, stk2;
33     TreeNode *cur;
34     stk1.push(root);
35     while (!stk1.empty()) {
36         cur = stk1.top();
37         stk1.pop();
38         stk2.push(cur);
39         if (cur->left)
40             stk1.push(cur->left);
41         if (cur->right)
42             stk1.push(cur->right);
43     }
44     while (!stk2.empty()) {
45         cout << stk2.top()->val << " ";
46         stk2.pop();
47     }
48 }

Morris方法：

morris方法的后序遍历较为复杂，因为需要逆序输出右孩子到父亲结点；

遍历过程与先序与中序类似，

当前驱结点的右孩子为当前结点时，左子树已经遍历完成，逆序输出当前结点的左孩子到前驱结点；

类似于链表的反转，不过反转输出之后，记得要反转回来。

 1 void reverse(TreeNode *begin, TreeNode *end) {
 2     if (begin == end)
 3         return;
 4     TreeNode *pre = begin;
 5     TreeNode *cur = begin->right;
 6     TreeNode *next;
 7     while (pre != end) {
 8         temp = cur->right;
 9         cur->right = pre;
10         pre = cur;
11         cur = temp;
12     }
13 }
14 
15 void traversalReversal(TreeNode *begin, TreeNode *end) {
16     reverse(begin, end);
17     TreeNode *it = end;
18     while (true) {
19         cout << it->val << " ";
20         if (it == begin)
21             break;
22         it = it->right;
23     }
24     reverse(end, begin);
25 }
26 
27 void postOrderMorris(TreeNode *root) {
28     if (!root)
29         return;
30     TreeNode dump(0);
31     dump.left = root;
32     TreeNode *cur = &dump;
33     TreeNode *pre = NULL;
34     while (cur) {
35         if (cur->left == NULL) {
36             cur = cur->right;
37         }
38         else {
39             pre = cur->left;
40             while (pre->right != NULL && pre->right != cur)
41                 pre = pre->right;
42             if (pre->right == NULL) {
43                 pre->right = cur;
44                 cur = cur->left;
45             }
46             else {
47                 traversalReverse(cur->left, pre);
48                 pre->right = NULL;
49                 cur = cur->right;
50             }
51         }
52     }
53 }

参考：

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

http://blog.csdn.net/hackbuteer1/article/details/6583988