二叉树的建立、四种遍历、求深度、求叶子结点数

  1 #include<stdio.h>
  2 #include<stdlib.h> 
  3 typedef struct Node{
  4     struct Node *lchild, *rchild;
  5     char data;
  6 }BiNode, *BiTree;
  7 BiTree CreatBiTree(BiTree *T)//前序建树,输入的是扩展二叉树 
  8 {
  9     char a;
 10     scanf("%c", &a);
 11     if(a == '#') *T = NULL;
 12     else{
 13         *T = (BiNode *)malloc(sizeof(BiNode));
 14         (*T)->data = a;
 15         CreatBiTree(&(*T)->lchild);
 16         CreatBiTree(&(*T)->rchild);
 17     }
 18     return *T;
 19 } 
 20 void PreOrder(BiTree T)
 21 {
 22     if(T){
 23         printf("%c ", T->data);
 24         PreOrder(T->lchild);
 25         PreOrder(T->rchild);
 26     }
 27 }
 28 void InOrder(BiTree T)
 29 {
 30     if(T){
 31         InOrder(T->lchild);
 32         printf("%c ", T->data);
 33         InOrder(T->rchild);
 34     }
 35 }
 36 void PostOrder(BiTree T)
 37 {
 38     if(T){
 39         PostOrder(T->lchild);
 40         PostOrder(T->rchild);
 41         printf("%c ", T->data);
 42     }
 43 }  
 44 void LevelOrder(BiTree T)//注意这里开的队列一定要是结构体型，因为要寻左右孩子 
 45 {
 46     BiNode *q[100];
 47     int front=0, rear=0;
 48     q[rear++] = T;
 49     while(front != rear){
 50         BiNode *t = q[front++];
 51         printf("%c ", t->data);
 52         if(t->lchild) q[rear++] = t->lchild;
 53         if(t->rchild) q[rear++] = t->rchild;
 54     }
 55 }
 56 int cal_depth(BiTree T)//求深度，思想是求出左右深度，再用大的加一 
 57 {
 58     if(!T) return 0;
 59     else{
 60         int h1 = cal_depth(T->lchild);
 61         int h2 = cal_depth(T->rchild);
 62         return h1>h2? h1+1:h2+1;//所以是先等两个调用出结果，再计算本层的深度 
 63     }
 64 } 
 65 int cal_leaves1(BiTree T, int *num)//第二个形参好像必须要有
 66 {
 67     if(!T->lchild&&!T->rchild) (*num)++;
 68     else{
 69         if(T->lchild) cal_leaves1(T->lchild, num);
 70         if(T->rchild) cal_leaves1(T->rchild, num);
 71     }
 72     return *num;//返回值要么不变要吗+1。返回值可以省略成void 
 73 } 
 74 int cal_leaves2(BiTree T)//*没想到 *
 75 {
 76     if(!T) return 0;
 77     else if(!T->lchild&&!T->rchild) return 1;
 78     else {
 79         return cal_leaves2(T->lchild)+cal_leaves2(T->rchild);
 80     }
 81 } 
 82 int main()
 83 {
 84     BiTree T;
 85     T = CreatBiTree(&T);
 86     PreOrder(T); 
 87     printf("---前序遍历
");
 88     InOrder(T);
 89     printf("---中序遍历
");
 90     PostOrder(T);
 91     printf("---后序遍历
");
 92     LevelOrder(T);
 93     printf("---层次遍历
");
 94     
 95     printf("二叉树深度：%d
", cal_depth(T));
 96     int n = 0;
 97     printf("叶子结点数(算法1)：%d
", cal_leaves1(T, &n)); 
 98     printf("叶子结点数(算法2)：%d
", cal_leaves2(T));
 99     return 0;
100 }
测试数据1：abc##de#f##g###