c语言编程之二叉树

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　利用链表建立二叉树，完成前序遍历、中序遍历、后序遍历。

　　建立二叉树用的是前序遍历建立二叉树：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<math.h>
  4 #include<malloc.h>
  5 
  6 
  7 typedef int element;
  8 typedef struct Tree{
  9         struct Tree *lchild,*rchild;
 10         char data;
 11 }*pTree,pNode;
 12 
 13 //char str[]="ABD#E##FG###CI##H##";
 14 char str[]="ABDH#K###E##CFI###G#J##";
 15 element index=0;
 16 //Init a empty tree
 17 element Init_tree(pTree *T)
 18         {
 19            *T=NULL;
 20            printf("init a empty tree\n");
 21         }
 22 
 23 //build a tree
 24 void Creat_tree(pNode **T)
 25         {
 26            char num;
 27            num=str[index++];
 28            pTree P=NULL;
 29            //P=*T;
 30            if(num=='#')
 31                 *T=NULL;
 32            else
 33              {
 34               // if(!(*T))
 35                 // exit(OVERFLOW);
 36                (*T)=(pTree)malloc(sizeof(pNode));
 37                //memset(*T,0,sizeof(pNode));
 38                (*T)->data=num;
 39                Creat_tree(&(*T)->lchild);
 40                Creat_tree(&(*T)->rchild);
 41              }
 42         }
 43 
 44 //pro order traversal
 45 element Pro_trav(pTree T)
 46         {
 47            if(T==NULL)
 48                 return ;
 49            printf("pro order traversal data:%c\n",T->data);
 50            Pro_trav(T->lchild);
 51            Pro_trav(T->rchild);
 52         }
 53 
 54 //midle order traversal
 55 element Mid_trav(pTree T)
 56         {
 57            if(T==NULL)
 58                 return;
 59            Mid_trav(T->lchild);
 60            printf("mid order traversal data:%c\n",T->data);
 61            Mid_trav(T->rchild);
 62         }
 63 
 64 //after traversal
 65 element Aft_trav(pTree T)
 66         {
 67            if(T==NULL)
 68                 return;
 69            Aft_trav(T->lchild);
 70            Aft_trav(T->rchild);
 71            printf("after order traversal data:%c\n",T->data);
 72         }
 73 
 74 element main()
 75         {
 76            pTree T;
 77            T=(pTree)malloc(sizeof(struct Tree));
 78            //Init_tree(&T);
 79            printf("before is ok\n");
 80            Creat_tree(&T);
 81            Pro_trav(T);
 82            Mid_trav(T);
 83            Aft_trav(T);
 84            return 0;
 85         }
 86

　　输出结果：

 1 before is ok
 2 pro order traversal data:A
 3 pro order traversal data:B
 4 pro order traversal data:D
 5 pro order traversal data:H
 6 pro order traversal data:K
 7 pro order traversal data:E
 8 pro order traversal data:C
 9 pro order traversal data:F
10 pro order traversal data:I
11 pro order traversal data:G
12 pro order traversal data:J
13 mid order traversal data:H
14 mid order traversal data:K
15 mid order traversal data:D
16 mid order traversal data:B
17 mid order traversal data:E
18 mid order traversal data:A
19 mid order traversal data:I
20 mid order traversal data:F
21 mid order traversal data:C
22 mid order traversal data:G
23 mid order traversal data:J
24 after order traversal data:K
25 after order traversal data:H
26 after order traversal data:D
27 after order traversal data:E
28 after order traversal data:B
29 after order traversal data:I
30 after order traversal data:F
31 after order traversal data:J
32 after order traversal data:G
33 after order traversal data:C
34 after order traversal data:A