[Alg] 二叉树的非递归遍历

1. 非递归遍历二叉树算法 (使用stack)

以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访问过得节点。

(1) 前序遍历

从整棵树的根节点开始，对于任意节点V，访问节点V并将节点V入栈，并判断节点V的左子节点L是否为空。若L不为空，则将L置为当前节点V；若L为空，则取出栈顶节点，并将栈顶结点的右子节点置为当前节点V。重复上述操作，直到当前节点V为空并且栈为空，遍历结束。

(2) 中序遍历

从整棵树的根节点开始，对于任意节点V，判断其左子节点L是否为空。若L不为空，则将V入栈并将L置为当前节点V；若L为空，则取出栈顶节点并访问该栈顶节点，然后将其右子节点置为当前节点V。重复上述操作，直到当前节点V为空节点且栈为空，遍历结束。

(3) 后序遍历

首先将整颗二叉树的根节点入栈。取栈顶节点V，若V不存在左子节点和右子节点，或V存在左子节点或右子节点但其左子节点和右子节点都被访问过了，则访问节点V，并将V从栈中弹出。若非上述两种情况，则将V的右子节点和左子节点(注意先右后左，这样出栈时才能先左后右)依次入栈。重复上述操作，直到栈为空，遍历结束。

2. 二叉树递归与非递归遍历代码

  1 #include "stdafx.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <string.h>
  5 
  6 
  7 #define Stack_increment 20
  8 #define Stack_Size 100  
  9 
 10 
 11 typedef struct  Tree
 12 {
 13     char data;
 14     struct Tree *lchild;
 15     struct Tree *rchild;
 16 }Node;
 17 
 18 Node* createBinaryTree()
 19 {
 20     Node *root;
 21     char ch;
 22     scanf("%c", &ch);
 23 
 24     if (ch == '#')
 25     {
 26         root = NULL;
 27     }
 28     else
 29     {
 30         root = (Node *)malloc(sizeof(Node));
 31         root -> data = ch;
 32         root -> lchild = createBinaryTree();
 33         root -> rchild = createBinaryTree();        
 34     }
 35 
 36     return root;
 37 }
 38 
 39 typedef struct 
 40 {
 41     int top;
 42     Node* arr[Stack_Size]; 
 43 }Stacktree;
 44 
 45 void InitStack(Stacktree *S)
 46 {
 47     S->top = 0;
 48 }
 49 
 50 void Push(Stacktree* S, Node* x)
 51 {
 52     int top1 = S -> top;
 53     if (x -> data == '#')
 54     {
 55         return;
 56     }
 57     else
 58     {
 59         S -> arr[top1++] = x;
 60         S -> top++;
 61     }
 62 }
 63 
 64 int Pop(Stacktree *S)
 65 {
 66     int top = S -> top;
 67     if (S->top == 0)
 68     {
 69         return 0;
 70     }
 71     else
 72     {
 73         --(S->top);
 74         return 1;
 75     }
 76 }
 77 
 78 Node* GetTop(Stacktree *S)
 79 {
 80     int top1 = S -> top;
 81     Node*p;
 82     p = S -> arr[top1--];
 83     return p;
 84 }
 85 
 86 Node* GetTop1(Stacktree *S)
 87 {
 88     int top1 = S -> top;
 89     Node*p;
 90     top1--;
 91     p = S -> arr[top1];
 92     return p;
 93 }
 94 
 95 int IsEmpty(Stacktree *S)
 96 {
 97     return(S->top == 0 ? 1 : 0);
 98 }
 99 
100 void preorderRecursive(Node *p )
101 {
102     if (p != NULL)
103     {
104         printf("%c ", p -> data);
105         preorderRecursive(p -> lchild);
106         preorderRecursive(p -> rchild);
107     }
108 }
109 
110 void inorderRecursive(Node *p )
111 {
112     if (p != NULL)
113     {
114         inorderRecursive(p -> lchild);
115         printf("%c ", p -> data);
116         inorderRecursive(p -> rchild);
117     }
118 }
119 
120 void postorderRecursive(Node *p )
121 {
122     if (p != NULL)
123     {
124         postorderRecursive(p -> lchild);
125         postorderRecursive(p -> rchild);
126         printf("%c ", p -> data);
127     }
128 }
129 
130 void preordernotRecursive(Node *p)
131 {
132     if(p)
133     {
134         Stacktree stree ;
135         InitStack(&stree);
136         Node *root = p;
137         while(root != NULL || !IsEmpty(&stree))
138         {
139             while(root != NULL)
140             {
141                 printf("%c  ", root->data);
142                 Push(&stree, root);
143                 root = root -> lchild;
144             }
145 
146             if(!IsEmpty(&stree))
147             {
148                 Pop(&stree);
149                 root = GetTop(&stree);
150                 root = root -> rchild;
151             }
152         }
153     }
154 }
155 
156 void inordernotRecursive(Node *p)
157 {
158     if(p)
159     {
160         Stacktree stree;
161         InitStack(&stree);
162         Node *root = p;
163         while(root != NULL || !IsEmpty(&stree))
164         {
165             while(root != NULL)
166             {
167                 Push(&stree, root);
168                 root = root -> lchild;
169             }
170 
171             if(!IsEmpty(&stree))
172             {
173                 Pop(&stree);
174                 root = GetTop(&stree);
175                 printf("%c  ", root -> data);
176                 root = root -> rchild;
177             }
178         }
179     }
180 }
181 
182 void postordernotRecursive(Node *p)
183 {
184     Stacktree stree;
185     InitStack(&stree);
186 
187     Node *root;    
188     Node *pre = NULL;    
189 
190     Push(&stree, p);
191 
192     while (!IsEmpty(&stree))
193     {
194         root = GetTop1(&stree);
195 
196         if ((root -> lchild == NULL && root -> rchild == NULL) || (pre != NULL && (pre == root -> lchild || pre == root -> rchild)))
197         {
198             printf("%c ", root -> data);
199             Pop(&stree);
200             pre = root;
201         }
202 
203         else
204         {
205             if (root -> rchild != NULL)
206             {
207                 Push(&stree, root -> rchild);
208             }
209 
210             if (root -> lchild != NULL)
211             {
212                 Push(&stree, root -> lchild);
213             }
214         }
215 
216     }
217 }
218 
219 void main()
220 {
221 
222     printf("请输入二叉树，'#'为空
");   
223     Node *root = createBinaryTree();
224 
225     printf("
递归先序遍历:
");
226     preorderRecursive(root);
227 
228     printf("
递归中序遍历:
");
229     inorderRecursive(root);
230 
231     printf("
递归后序遍历:
");
232     postorderRecursive(root);
233 
234     printf("
非递归先序遍历
");
235     preordernotRecursive(root);
236 
237     printf("
非递归中序遍历
");
238     inordernotRecursive(root);
239 
240     printf("
非递归后序遍历
");
241     postordernotRecursive(root);
242 
243     getchar();
244     getchar();
245 }

(代码中的top是栈顶元素的上一位的index，不是栈顶元素的index～)

input:

ABC##D##E##

output:

递归先序遍历:

A B C D E

递归中序遍历:

C B D A E

递归后序遍历:

C D B E A

非递归先序遍历:

A B C D E

非递归中序遍历:

C B D A E

非递归后序遍历:

C D B E A

3. Morris Traversal (遍历二叉树无需stack)

Morris Traversal 是一种非递归无需栈仅在常量空间复杂度的条件下即可实现二叉树遍历的一种很巧妙的方法。该方法的实现需要构造一种新型的树结构，Threaded Binary Tree.

3.1 Threaded Binary Tree 定义

Threaded binary tree: A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node. ~WIkipedia

Threaded binary tree 的构造相当于将所有原本为空的右子节点指向了中序遍历的该点的后续节点，把所有原本为空的左子节点都指向了中序遍历的该点前序节点。如图1所示。

那么通过这种方式，对于当前节点cur, 若其右子树为空，(cur -> right = NULL)，那么通过沿着其pre指针，即可返回其根节点继续遍历。

比如对于图1中的节点A，其右孩子为空，则说明以A为根节点的子树遍历完成，沿着其pre指针可以回到A的根节点B，继续遍历。这里的pre指针相当于保存了当前节点的回溯的位置信息。

图1. Threaded binary tree 图2. Threaded tree构造及遍历算法图示

3.2 Threaded Binary Tree 算法实现

3.2.1 算法描述

1. 初始化指针cur = root

2. while (cur != NULL)

2.1 if cur -> left == NULL

a) print(cur -> val)

b) cur = cur -> right

2.2 else if cur -> left != NULL

将pre 指向cur 的左子树中的最右子节点 (并保证不指回cur)

2.2.1 if pre -> right == NULL

a) pre -> right = cur

b) cur = cur -> left

2.2.2 else if pre -> right != NULL (说明pre -> right是用于指回cur节点的指针)

a) 将pre -> right 置空

　　　　　 b) print(cur -> val)

　　　　 c) cur = cur -> right

3.2.2 代码实现 (中序)

 1 # include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct TreeNode
 5 {
 6     int val;
 7     struct TreeNode *right;
 8     struct TreeNode *left;
 9     TreeNode(int x): val(x), left(NULL), right(NULL) {}
10 };
11 
12 vector<int> inorderTraversal(TreeNode *root)
13 {
14     vector<int> res;
15     if(!root) return res;
16     TreeNode *cur, *pre;
17     cur = root;
18 
19     while(cur)
20     {
21         if(cur -> left == NULL)
22         {
23             res.push_back(cur -> val);
24             cur = cur -> right;
25         }
26 
27         else if(cur -> left != NULL)
28         {
29             pre = cur -> left;
30             while(pre -> right && pre -> right != cur) pre = pre -> right;
31             if(pre -> right == NULL)
32             {
33                 pre -> right = cur;
34                 cur = cur -> left;
35             }
36             else if(pre -> right != NULL)
37             {
38                 pre -> right = NULL;
39                 res.push_back(cur -> val);
40                 cur = cur -> right;
41             }
42         }
43     }
44     return res;
45 }
46 
47 int main()
48 {
49     vector<int> res;
50     TreeNode *node1 = new TreeNode(1);
51     TreeNode *node2 = new TreeNode(2);
52     TreeNode *node3 = new TreeNode(3);
53     TreeNode *node4 = new TreeNode(4);
54     node1 -> left = node2;
55     node2 -> left = node3;
56     node3 -> right = node4;
57     inorderTraversal(node1);
58     res = inorderTraversal(node1);
59     vector<int>::iterator it;
60     for(it = res.begin(); it != res.end(); ++it)
61     {
62         cout << *it << " ";
63     }
64     cout << endl;
65     delete node1; delete node2;
66     delete node3; delete node4;
67     return 0;
68 }
69 
70 // 3 4 2 1

参考：

1. 以先序、中序、后序的方式递归非递归遍历二叉树：https://blog.csdn.net/asd20172016/article/details/80786186

2. Morris Traversal: [LeetCode] Binary Tree Inorder Traversal 二叉树的中序遍历: https://www.cnblogs.com/grandyang/p/4297300.html

3. [LeetCode] Recover Binary Search Tree 复原二叉搜索树: https://www.cnblogs.com/grandyang/p/4298069.html

4. Wikipedia: Threaded binary tree: https://en.wikipedia.org/wiki/Threaded_binary_tree