zhihe网站建设 淘宝,自己做网站成本,wordpress调用评论,wordpress在php什么版本1. 非递归遍历二叉树算法 (使用stack) 以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访问过得节点。 (1) 前序遍历 从整棵树的根节点开始#xff0c;对于任意节点V#xff0c;访问节点V并将节点V入栈#xff0c;并判断节点V的左子节点L是否为空。若L不为空#… 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.h2 #include stdio.h3 #include stdlib.h4 #include string.h5 6 7 #define Stack_increment 208 #define Stack_Size 100 9 10 11 typedef struct Tree12 {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 else29 {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 else58 {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 else72 {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.h2 using namespace std;3 4 struct TreeNode5 {6 int val;7 struct TreeNode *right;8 struct TreeNode *left;9 TreeNode(int x): val(x), left(NULL), right(NULL) {}
10 };
11
12 vectorint inorderTraversal(TreeNode *root)
13 {
14 vectorint 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 vectorint 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 vectorint::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
