最基礎的算法練習1，基礎算法練習1
二叉樹的幾種遞歸和非遞歸式遍歷：
![]()
1 #include <fstream>
2 #include <iostream>
3
4 using namespace std;
5
6 /*
7 後序遍歷的非遞歸實現是三種遍歷方式中最難的一種。因為在後序遍歷中，要保證左孩子和右孩子都已被訪問並且左孩子在右孩子
8 前訪問才能訪問根結點，這就為流程的控制帶來了難題。下面介紹兩種思路。
9 第一種思路：對於任一結點P，將其入棧，然後沿其左子樹一直往下搜索，直到搜索到沒有左孩子的結點，此時該結點出現在棧頂，
10 但是此時不能將其出棧並訪問，因此其右孩子還為被訪問。所以接下來按照相同的規則對其右子樹進行相同的處理，當訪問完其右孩子
11 時，該結點又出現在棧頂，此時可以將其出棧並訪問。這樣就保證了正確的訪問順序。可以看出，在這個過程中，每個結點都兩次出現
12 在棧頂，只有在第二次出現在棧頂時，才能訪問它。因此需要多設置一個變量標識該結點是否是第一次出現在棧頂。
13 第二種思路：要保證根結點在左孩子和右孩子訪問之後才能訪問，因此對於任一結點P，先將其入棧。如果P不存在左孩子和右孩子，
14 則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。若非上述兩種
15 情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結
16 點前面被訪問。
17 */
18
19 #define queue_len 100
20
21 struct node
22 {
23 char c;
24 struct node *lch,*rch;
25 bool flag;
26 node():flag(0){}
27 void get_c()
28 {
29 printf("%c",c);
30 }
31 };
32
33 node* set_tree();//建樹
34 void pre_order(node* tree);//先序遍歷
35 void in_order(node* tree);//中序遍歷
36 void post_order(node* tree);//後序遍歷
37 void level_order(node* tree);//層次遍歷
38 void nr_pre_order(node* tree);//非遞歸先序遍歷
39 void nr_in_order(node* tree);//非遞歸中序遍歷
40 void nr_post_order_1(node* tree);//非遞歸後序遍歷
41 void nr_post_order_2(node* tree);//非遞歸後序遍歷
42
43 int main()
44 {
45 //freopen("D:\\input.in","r",stdin);
46 //freopen("D:\\output.out","w",stdout);
47 node* tree=set_tree();
48 printf("先序遍歷：");
49 pre_order(tree);
50 puts("");
51 printf("中序遍歷：");
52 in_order(tree);
53 puts("");
54 printf("後序遍歷：");
55 post_order(tree);
56 puts("");
57 printf("層次遍歷：");
58 level_order(tree);
59 puts("");
60 printf("先序遍歷：");
61 nr_pre_order(tree);
62 puts("");
63 printf("中序遍歷：");
64 nr_in_order(tree);
65 puts("");
66 printf("後序遍歷：");
67 nr_post_order_1(tree);
68 puts("");
69 printf("後序遍歷：");
70 nr_post_order_2(tree);
71 puts("");
72 return 0;
73 }
74 node* set_tree()
75 {
76 node* p,*s;
77 node* gen=new node;
78 gen->c='A';
79
80 gen->lch=new node;
81 p=gen->lch;
82 p->c='B';
83 p->rch=NULL;
84 p->lch=new node;
85 p=p->lch;
86 p->c='D';
87 p->lch=NULL;
88 p->rch=new node;
89 p=p->rch;
90 p->c='G';
91 p->lch=NULL;
92 p->rch=NULL;
93
94 gen->rch=new node;
95 p=gen->rch;
96 p->c='C';
97 p->lch=new node;
98 s=p->lch;
99 s->c='E';
100 s->lch=NULL;
101 s->rch=NULL;
102 p->rch=new node;
103 s=p->rch;
104 s->c='F';
105 s->lch=NULL;
106 s->rch=NULL;
107
108 return gen;
109 }
110 void pre_order(node* tree)
111 {
112 if(tree!=NULL)
113 {
114 tree->get_c();
115 pre_order(tree->lch);
116 pre_order(tree->rch);
117 }
118 }
119 void in_order(node* tree)
120 {
121 if(tree!=NULL)
122 {
123 in_order(tree->lch);
124 tree->get_c();
125 in_order(tree->rch);
126 }
127 }
128 void post_order(node* tree)
129 {
130 if(tree!=NULL)
131 {
132 post_order(tree->lch);
133 post_order(tree->rch);
134 tree->get_c();
135 }
136 }
137 void level_order(node* tree)
138 {
139 node* queue_1[queue_len];
140 int front,rear;
141
142 if(tree==NULL) return;
143 front=-1;
144 rear=0;
145 queue_1[rear]=tree;
146 while(front!=rear)
147 {
148 front++;
149 queue_1[front]->get_c();
150
151 if(queue_1[front]->lch!=NULL)
152 {
153 rear++;
154 queue_1[rear]=queue_1[front]->lch;
155 }
156 if(queue_1[front]->rch!=NULL)
157 {
158 rear++;
159 queue_1[rear]=queue_1[front]->rch;
160 }
161 }
162 }
163 void nr_pre_order(node* tree)
164 {
165 node* stack_1[queue_len];
166 int top=-1;
167
168 if(tree==NULL) return;
169 node* p=tree;
170 while(p!=NULL||top!=-1)
171 {
172 while(p!=NULL)
173 {
174 p->get_c();
175 stack_1[++top]=p;
176 p=p->lch;
177 }
178 if(top==-1) return;
179 p=stack_1[top--]->rch;
180 }
181 }
182 void nr_in_order(node* tree)
183 {
184 node* stack_1[queue_len];
185 int top=-1;
186
187 if(tree==NULL) return;
188 node* p=tree;
189 while(p!=NULL||top!=-1)
190 {
191 while(p!=NULL)
192 {
193 stack_1[++top]=p;
194 p=p->lch;
195 }
196 if(top==-1) return;
197 stack_1[top]->get_c();
198 p=stack_1[top--]->rch;
199 }
200 }
201 void nr_post_order_1(node* tree)
202 {
203 node* stack_1[queue_len];
204 int top=-1;
205
206 if(tree==NULL) return;
207 node* p=tree;
208 while(p!=NULL||top!=-1)
209 {
210 while(p!=NULL)
211 {
212 stack_1[++top]=p;
213 p=p->lch;
214 }
215 if(top==-1) return;
216 p=stack_1[top];
217 if(p->flag==0) {p->flag=1;p=p->rch;}
218 else { p->get_c(),top--;p=NULL;}
219 }
220 }
221 void nr_post_order_2(node* tree)
222 {
223 node* stack_1[queue_len];
224 int top=0;
225
226 if(tree==NULL) return;
227 node* p=tree;
228 while(top!=-1)
229 {
230 p=stack_1[top];
231 if((p->lch==NULL||p->lch->flag==0)&&(p->rch==NULL||p->rch->flag==0))
232 {
233 p->get_c();
234 p->flag=0;
235 top--;
236 }
237 else
238 {
239 if(p->rch!=NULL)
240 {
241 stack_1[++top]=p->rch;
242 }
243 if(p->lch!=NULL)
244 {
245 stack_1[++top]=p->lch;
246 }
247 }
248 }
249 }
View Code
