#morris traversal
轉載：http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
本文主要解決一個問題，如何實現(xiàn)二叉樹的前中后序遍歷，有兩個要求：
\1. O(1)空間復雜度，即只能使用常數(shù)空間；
\2. 二叉樹的形狀不能被破壞（中間過程允許改變其形狀）。
通常，實現(xiàn)二叉樹的前序（preorder）、中序（inorder）、后序（postorder）遍歷有兩個常用的方法：一是遞歸(recursive)，二是使用棧實現(xiàn)的迭代版本(stack+iterative)。這兩種方法都是O(n)的空間復雜度（遞歸本身占用stack空間或者用戶自定義的stack），所以不滿足要求。（用這兩種方法實現(xiàn)的中序遍歷實現(xiàn)可以參考這里。）
Morris Traversal方法可以做到這兩點，與前兩種方法的不同在于該方法只需要O(1)空間，而且同樣可以在O(n)時間內完成。
要使用O(1)空間進行遍歷，最大的難點在于，遍歷到子節(jié)點的時候怎樣重新返回到父節(jié)點（假設節(jié)點中沒有指向父節(jié)點的p指針），由于不能用棧作為輔助空間。為了解決這個問題，Morris方法用到了線索二叉樹（threaded binary tree）的概念。在Morris方法中不需要為每個節(jié)點額外分配指針指向其前驅（predecessor）和后繼節(jié)點（successor），只需要利用葉子節(jié)點中的左右空指針指向某種順序遍歷下的前驅節(jié)點或后繼節(jié)點就可以了。
Morris只提供了中序遍歷的方法，在中序遍歷的基礎上稍加修改可以實現(xiàn)前序，而后續(xù)就要再費點心思了。所以先從中序開始介紹。
首先定義在這篇文章中使用的二叉樹節(jié)點結構，即由val，left和right組成：
1 struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };
一、中序遍歷
步驟：
\1. 如果當前節(jié)點的左孩子為空，則輸出當前節(jié)點并將其右孩子作為當前節(jié)點。
\2. 如果當前節(jié)點的左孩子不為空，在當前節(jié)點的左子樹中找到當前節(jié)點在中序遍歷下的前驅節(jié)點。
a) 如果前驅節(jié)點的右孩子為空，將它的右孩子設置為當前節(jié)點。當前節(jié)點更新為當前節(jié)點的左孩子。
b) 如果前驅節(jié)點的右孩子為當前節(jié)點，將它的右孩子重新設為空（恢復樹的形狀）。輸出當前節(jié)點。當前節(jié)點更新為當前節(jié)點的右孩子。
\3. 重復以上1、2直到當前節(jié)點為空。
圖示：
下圖為每一步迭代的結果（從左至右，從上到下），cur代表當前節(jié)點，深色節(jié)點表示該節(jié)點已輸出。
代碼：
[
](javascript:void(0);)
1 void inorderMorrisTraversal(TreeNode *root) {
2 TreeNode *cur = root, *prev = NULL;
3 while (cur != NULL)
4 {
5 if (cur->left == NULL) // 1.
6 {
7 printf("%d ", cur->val);
8 cur = cur->right;
9 }
10 else
11 {
12 // find predecessor
13 prev = cur->left;
14 while (prev->right != NULL && prev->right != cur)
15 prev = prev->right;
16
17 if (prev->right == NULL) // 2.a)
18 {
19 prev->right = cur;
20 cur = cur->left;
21 }
22 else // 2.b)
23 {
24 prev->right = NULL;
25 printf("%d ", cur->val);
26 cur = cur->right;
27 }
28 }
29 }
30 }
](javascript:void(0);)
復雜度分析：
空間復雜度：O(1)，因為只用了兩個輔助指針。
時間復雜度：O(n)。證明時間復雜度為O(n)，最大的疑惑在于尋找中序遍歷下二叉樹中所有節(jié)點的前驅節(jié)點的時間復雜度是多少，即以下兩行代碼：
1 while (prev->right != NULL && prev->right != cur)
2 prev = prev->right;
直覺上，認為它的復雜度是O(nlgn)，因為找單個節(jié)點的前驅節(jié)點與樹的高度有關。但事實上，尋找所有節(jié)點的前驅節(jié)點只需要O(n)時間。n個節(jié)點的二叉樹中一共有n-1條邊，整個過程中每條邊最多只走2次，一次是為了定位到某個節(jié)點，另一次是為了尋找上面某個節(jié)點的前驅節(jié)點，如下圖所示，其中紅色是為了定位到某個節(jié)點，黑色線是為了找到前驅節(jié)點。所以復雜度為O(n)。
二、前序遍歷
前序遍歷與中序遍歷相似，代碼上只有一行不同，不同就在于輸出的順序。
步驟：
\1. 如果當前節(jié)點的左孩子為空，則輸出當前節(jié)點并將其右孩子作為當前節(jié)點。
\2. 如果當前節(jié)點的左孩子不為空，在當前節(jié)點的左子樹中找到當前節(jié)點在中序遍歷下的前驅節(jié)點。
a) 如果前驅節(jié)點的右孩子為空，將它的右孩子設置為當前節(jié)點。輸出當前節(jié)點（在這里輸出，這是與中序遍歷唯一一點不同）。當前節(jié)點更新為當前節(jié)點的左孩子。
b) 如果前驅節(jié)點的右孩子為當前節(jié)點，將它的右孩子重新設為空。當前節(jié)點更新為當前節(jié)點的右孩子。
\3. 重復以上1、2直到當前節(jié)點為空。
圖示：
代碼：
[](javascript:void(0);)
1 void preorderMorrisTraversal(TreeNode *root) {
2 TreeNode *cur = root, *prev = NULL;
3 while (cur != NULL)
4 {
5 if (cur->left == NULL)
6 {
7 printf("%d ", cur->val);
8 cur = cur->right;
9 }
10 else
11 {
12 prev = cur->left;
13 while (prev->right != NULL && prev->right != cur)
14 prev = prev->right;
15
16 if (prev->right == NULL)
17 {
18 printf("%d ", cur->val); // the only difference with inorder-traversal
19 prev->right = cur;
20 cur = cur->left;
21 }
22 else
23 {
24 prev->right = NULL;
25 cur = cur->right;
26 }
27 }
28 }
29 }
](javascript:void(0);)
復雜度分析：
時間復雜度與空間復雜度都與中序遍歷時的情況相同。
三、后序遍歷
后續(xù)遍歷稍顯復雜，需要建立一個臨時節(jié)點dump，令其左孩子是root。并且還需要一個子過程，就是倒序輸出某兩個節(jié)點之間路徑上的各個節(jié)點。
步驟：
當前節(jié)點設置為臨時節(jié)點dump。
\1. 如果當前節(jié)點的左孩子為空，則將其右孩子作為當前節(jié)點。
\2. 如果當前節(jié)點的左孩子不為空，在當前節(jié)點的左子樹中找到當前節(jié)點在中序遍歷下的前驅節(jié)點。
a) 如果前驅節(jié)點的右孩子為空，將它的右孩子設置為當前節(jié)點。當前節(jié)點更新為當前節(jié)點的左孩子。
b) 如果前驅節(jié)點的右孩子為當前節(jié)點，將它的右孩子重新設為空。倒序輸出從當前節(jié)點的左孩子到該前驅節(jié)點這條路徑上的所有節(jié)點。當前節(jié)點更新為當前節(jié)點的右孩子。
\3. 重復以上1、2直到當前節(jié)點為空。
圖示：
代碼：
[](javascript:void(0);)
1 void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
2 {
3 if (from == to)
4 return;
5 TreeNode *x = from, *y = from->right, *z;
6 while (true)
7 {
8 z = y->right;
9 y->right = x;
10 x = y;
11 y = z;
12 if (x == to)
13 break;
14 }
15 }
16
17 void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.
18 {
19 reverse(from, to);
20
21 TreeNode *p = to;
22 while (true)
23 {
24 printf("%d ", p->val);
25 if (p == from)
26 break;
27 p = p->right;
28 }
29
30 reverse(to, from);
31 }
32
33 void postorderMorrisTraversal(TreeNode *root) {
34 TreeNode dump(0);
35 dump.left = root;
36 TreeNode *cur = &dump, *prev = NULL;
37 while (cur)
38 {
39 if (cur->left == NULL)
40 {
41 cur = cur->right;
42 }
43 else
44 {
45 prev = cur->left;
46 while (prev->right != NULL && prev->right != cur)
47 prev = prev->right;
48
49 if (prev->right == NULL)
50 {
51 prev->right = cur;
52 cur = cur->left;
53 }
54 else
55 {
56 printReverse(cur->left, prev); // call print
57 prev->right = NULL;
58 cur = cur->right;
59 }
60 }
61 }
62 }
](javascript:void(0);)
復雜度分析：
空間復雜度同樣是O(1)；時間復雜度也是O(n)，倒序輸出過程只不過是加大了常數(shù)系數(shù)。
注：
以上所有的代碼以及測試代碼可以在我的Github里獲取。
參考：
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://www.geeksforgeeks.org/morris-traversal-for-preorder/
http://stackoverflow.com/questions/6478063/how-is-the-complexity-of-morris-traversal-on
http://blog.csdn.net/wdq347/article/details/8853371
Data Structures and Algorithms in C++ by Adam Drozdek
---------------
以前我只知道遞歸和棧+迭代實現(xiàn)二叉樹遍歷的方法，昨天才了解到有使用O(1)空間復雜度的方法。以上都是我參考了網(wǎng)上的資料加上個人的理解來總結，如果有什么不對的地方非常歡迎大家的指正。
