利用链表建立二叉树，完成前序遍历、中序遍历、后序遍历。
建立二叉树用的是前序遍历建立二叉树：
1 #include2 #include 3 #include 4 #include 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:F10 pro order traversal data:I11 pro order traversal data:G12 pro order traversal data:J13 mid order traversal data:H14 mid order traversal data:K15 mid order traversal data:D16 mid order traversal data:B17 mid order traversal data:E18 mid order traversal data:A19 mid order traversal data:I20 mid order traversal data:F21 mid order traversal data:C22 mid order traversal data:G23 mid order traversal data:J24 after order traversal data:K25 after order traversal data:H26 after order traversal data:D27 after order traversal data:E28 after order traversal data:B29 after order traversal data:I30 after order traversal data:F31 after order traversal data:J32 after order traversal data:G33 after order traversal data:C34 after order traversal data:A