树和二叉树（代码）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int ElementType;
  5 
  6 typedef struct TreeNode {
  7     ElementType Data;
  8     struct TreeNode *Left;
  9     struct TreeNode *Right;
 10 }*BinTree, *Position;
 11 
 12 Position createBinNode(ElementType data)
 13 {
 14     Position T;
 15 
 16     T = (Position)malloc(sizeof(struct TreeNode));
 17     if(T == NULL)
 18     {
 19         return NULL;
 20     }
 21     T->Left  = NULL;
 22     T->Right = NULL;
 23     T->Data  = data;
 24 
 25     return T;
 26 }
 27 
 28 // 二叉树的递归遍历
 29 void PreOrderTraversal(BinTree Bt)
 30 {
 31     if(Bt)
 32     {
 33         printf("%c ", Bt->Data);
 34         PreOrderTraversal(Bt->Left);
 35         PreOrderTraversal(Bt->Right);
 36     }
 37 }
 38 
 39 #if 0
 40 void PreOrderTraversal_R2L(BinTree Bt)
 41 {
 42     if(Bt)
 43     {
 44         printf("%c ", Bt->Data);
 45         PreOrderTraversal_R2L(Bt->Right);
 46         PreOrderTraversal_R2L(Bt->Left);
 47     }
 48 }
 49 #endif
 50 
 51 void InOrderTraversal(BinTree Bt)
 52 {
 53     if(Bt)
 54     {
 55         InOrderTraversal(Bt->Left);
 56         printf("%c ", Bt->Data);
 57         InOrderTraversal(Bt->Right);
 58     }
 59 }
 60 
 61 void PostOrderTraversal(BinTree Bt)
 62 {
 63     if(Bt)
 64     {
 65         PostOrderTraversal(Bt->Left);
 66         PostOrderTraversal(Bt->Right);
 67         printf("%c ", Bt->Data);
 68     }
 69 }
 70 
 71 // 二叉树的非递归遍历
 72 void PreOrderTraversal_ext(BinTree Bt)
 73 {
 74     BinTree pStack[100];
 75     int top = -1;
 76     Position pBt = Bt;
 77 
 78     while(pBt != NULL || top > -1) /* Bt || !isEmpty(pStack) */
 79     {
 80         while(pBt)
 81         {
 82             // 与中序遍历不同点就是在第一次压栈的时候就进行访问了
 83             printf("%c ", pBt->Data);
 84             pStack[++top] = pBt;
 85             pBt = pBt->Left;
 86         }
 87         if(top > -1) /* !isEmpty(pStack) */
 88         {
 89             pBt = pStack[top--];
 90             //printf("%c ", pBt->Data);
 91             pBt = pBt->Right; /* 转向右子树 */
 92         }
 93     }
 94 }
 95 
 96 void InOrderTraversal_ext(BinTree Bt)
 97 {
 98     BinTree pStack[100];
 99     int top = -1;
100     Position pBt = Bt;
101 
102     // 当前访问的结点没有右子树的时候,就会出现pBt==NULL,但是栈不空的情况
103     while(pBt != NULL || top > -1) /* Bt || !isEmpty(pStack) */
104     {
105         // TODO: 1.遇到一个结点，就把它压栈，并去遍历它的左子树
106         while(pBt)
107         {
108             pStack[++top] = pBt;
109             pBt = pBt->Left;
110         }
111         // TODO: 2.当左子树遍历结束后，从栈顶弹出这个结点并访问它
112         if(top > -1) /* !isEmpty(pStack) */
113         {
114             pBt = pStack[top--];
115             printf("%c ", pBt->Data);
116             // TODO: 3.然后按其右指针再去中序遍历该结点的右子树
117             pBt = pBt->Right; /* 转向右子树 */
118         }
119     }
120 }
121 
122 void PostOrderTraversal_ext(BinTree Bt)
123 {
124     BinTree pStack[100];
125     int top = -1;
126     Position pBt = Bt;
127     Position pPre = NULL;
128 
129     // 先把根结点入栈
130     pStack[++top] = Bt;
131     while(top > -1)
132     {
133         // 只探测栈顶的结点是否满足被访问的条件
134         // 当前结点为叶结点 或者 当前结点的左孩子或右孩子已经被访问过来，则满足访问条件
135         // 怎么保证当前弹出栈的结点比其父结点先出的？
136         pBt = pStack[top];
137         if((pBt->Left == NULL && pBt->Right == NULL)
138             || (pPre != NULL && (pPre == pBt->Left || pPre == pBt->Right)))
139         {
140             printf("%c ", pBt->Data);
141             top--;
142             pPre = pBt;
143         }
144         else
145         {
146             if(pBt->Right != NULL)
147             {
148                 pStack[++top] = pBt->Right;
149             }
150             if(pBt->Left != NULL)
151             {
152                 pStack[++top] = pBt->Left;
153             }
154         }
155     }
156 }
157 
158 void LevelOrderTraversal(BinTree Bt)
159 {
160     BinTree pQueue[100];
161     int head = 0;
162     int tail = 0;
163     BinTree pBt;
164 
165     pQueue[tail++] = Bt;
166     while(tail != head)
167     {
168         pBt = pQueue[head++];
169         printf("%c ", pBt->Data);
170         if(pBt->Left != NULL)
171         {
172             pQueue[tail++] = pBt->Left;
173         }
174         if(pBt->Right != NULL)
175         {
176             pQueue[tail++] = pBt->Right;
177         }
178     }
179 }
180 
181 // 输出二叉树的叶子结点,无论前中后序,叶子的输出顺序都是一样的,从树的左到右.
182 void PreOrderPrintLeaves(BinTree Bt)
183 {
184     if(Bt)
185     {
186         if(Bt->Left == NULL && Bt->Right == NULL)
187             printf("%c ", Bt->Data);
188         PreOrderPrintLeaves(Bt->Left);
189         PreOrderPrintLeaves(Bt->Right);
190     }
191 }
192 
193 void InOrderPrintLeaves(BinTree Bt)
194 {
195     if(Bt)
196     {
197         InOrderPrintLeaves(Bt->Left);
198         if(Bt->Left == NULL && Bt->Right == NULL)
199             printf("%c ", Bt->Data);
200         InOrderPrintLeaves(Bt->Right);
201     }
202 }
203 
204 void PostOrderPrintLeaves(BinTree Bt)
205 {
206     if(Bt)
207     {
208         PostOrderPrintLeaves(Bt->Left);
209         PostOrderPrintLeaves(Bt->Right);
210         if(Bt->Left == NULL && Bt->Right == NULL)
211             printf("%c ", Bt->Data);
212     }
213 }
214 
215 // 求二叉树的叶结点个数
216 static int giNodeCnt = 0;
217 void PreOrderGetNodes(BinTree Bt)
218 {
219     if(Bt)
220     {
221         PreOrderGetNodes(Bt->Left);
222         PreOrderGetNodes(Bt->Right);
223         if(Bt->Left == NULL && Bt->Right == NULL)
224             giNodeCnt++;
225     }
226 }
227 
228 int BinTreeGetLeaves(BinTree Bt)
229 {
230     if(Bt == NULL)
231         return 0;
232     if(Bt->Left == NULL && Bt->Right == NULL)
233         return 1;
234     else
235         return BinTreeGetLeaves(Bt->Left) + BinTreeGetLeaves(Bt->Right);
236 }
237 
238 // 求二叉树的高度
239 int PostOrderGetHeight(BinTree Bt)
240 {
241     int HL, HR, MaxH;
242 
243     if(Bt)
244     {
245         HL = PostOrderGetHeight(Bt->Left);
246         HR = PostOrderGetHeight(Bt->Right);
247         MaxH = (HL > HR) ? HL : HR;
248         return (MaxH + 1);
249     }
250     else
251     {
252         return 0;
253     }
254 }
255 
256 int main(void)
257 {
258     int MaxH;
259     Position T1;
260     Position T21, T22;
261     Position T31, T32, T33, T34;
262     Position T41, T42, T43, T44, T45, T46, T47, T48;
263 
264     T1  = createBinNode(‘A‘);
265     T21 = createBinNode(‘B‘);
266     T22 = createBinNode(‘C‘);
267     T31 = createBinNode(‘D‘);
268     T32 = createBinNode(‘F‘);
269     T33 = createBinNode(‘G‘);
270     T34 = createBinNode(‘I‘);
271     T43 = createBinNode(‘E‘);
272     T46 = createBinNode(‘H‘);
273 
274     
275     T1->Left   = T21;
276     T1->Right  = T22;
277 
278     T21->Left  = T31;
279     T21->Right = T32;
280 
281     T22->Left  = T33;
282     T22->Right = T34;
283 
284     T32->Left  = T43;
285 
286     T33->Right = T46;
287     
288     printf("\n");
289     printf("PreOrderTraversal:\n");
290     PreOrderTraversal(T1);
291 
292     printf("\n");
293     printf("PreOrderTraversal_ext:\n");
294     PreOrderTraversal_ext(T1);
295 
296     //printf("\n");
297     //printf("PreOrderTraversal R->L:\n");
298     //PreOrderTraversal_R2L(T1);
299 
300     printf("\n");
301     printf("InOrderTraversal:\n");
302     InOrderTraversal(T1);
303 
304     printf("\n");
305     printf("InOrderTraversal_ext:\n");
306     InOrderTraversal(T1);
307 
308     printf("\n");
309     printf("PostOrderTraversal:\n");
310     PostOrderTraversal(T1);
311 
312     printf("\n");
313     printf("PostOrderTraversal_ext:\n");
314     PostOrderTraversal_ext(T1);
315 
316     printf("\n");
317     printf("LevelOrderTraversal:\n");
318     LevelOrderTraversal(T1);
319 
320     printf("\n");
321     printf("PreOrderPrintLeaves:\n");
322     PreOrderPrintLeaves(T1);
323     printf("\n");
324     printf("InOrderPrintLeaves:\n");
325     InOrderPrintLeaves(T1);
326     printf("\n");
327     printf("PostOrderPrintLeaves:\n");
328     PostOrderPrintLeaves(T1);
329 
330     printf("\n");
331     printf("PostOrderGetHeight::");
332     MaxH = PostOrderGetHeight(T1);
333     printf("%d\n", MaxH);
334 
335     printf("\n");
336     PreOrderGetNodes(T1);
337     printf("PreOrderNodes: %d\n", giNodeCnt);
338 
339     printf("\n");
340     printf("BinTreeGetLeaves: %d\n", BinTreeGetLeaves(T1));
341 
342     return 0;
343 }