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("請輸入二叉樹，'#'為空\n"); 223 Node *root = createBinaryTree(); 224 225 printf("\n遞歸先序遍歷:\n"); 226 preorderRecursive(root); 227 228 printf("\n遞歸中序遍歷:\n"); 229 inorderRecursive(root); 230 231 printf("\n遞歸后序遍歷:\n"); 232 postorderRecursive(root); 233 234 printf("\n非遞歸先序遍歷\n"); 235 preordernotRecursive(root); 236 237 printf("\n非遞歸中序遍歷\n"); 238 inordernotRecursive(root); 239 240 printf("\n非遞歸后序遍歷\n"); 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

轉載于:https://www.cnblogs.com/shiyublog/p/11256756.html

總結

以上是生活随笔為你收集整理的[Alg] 二叉树的非递归遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。