计算二叉树的深度和叶子结点数递归算法实现

【问题描述】

计算二叉树的深度和叶子结点数

【输入形式】

输入二叉树的先序遍历序列建立二叉树。

【输出形式】

输出二叉树的叶子结点数和深度。

【样例输入】

A

B

C

#

#

#

#

【样例输出】

Leaves:1

Depth:3

求给定二叉树的深度：

    二叉树的深度就是二叉树中结点的最大层次。如果二叉树是空树，则深度为0；否则，分别求二叉树根左子树和右子树的深度，取其中最大值加一就是该 二叉树的最大深度。

    递归计算公式为：Depth（T）={0；当T==NULL;                                                               }

                                                      {max(Depth(T->lchild),Depth(T->rchild)) 1;当T！=NULL;}

如下：

1.  
   int depth(BiTree t)
2.  
   {
3.  
   //此处补充代码，求取二叉树的深度
4.  
   int hl,hr;
5.  
   if(t==NULL)return 0; //若数为空则返回0
6.  
   else
7.  
   {
8.  
   hl=depth(t->lchild); //递归求左子树的深度
9.  
   hr=depth(t->rchild); //递归求右子树的深度
10.  
    if(hl>hr)return (hl 1);
11.  
    else return (hr 1);
12.  
    }
13.  
    }

求叶子结点数也可以通过递归的方法进行统计。

方法如下：

1.  
   int Leaves(BiTree t)
2.  
   {
3.  
   //此处补充代码，统计二叉树中叶子结点数
4.  
   int count1,count2;
5.  
   if(t==NULL)return 0; //数空
6.  
   else
7.  
   if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点
8.  
   else
9.  
   {
10.  
    count1=Leaves(t->lchild);//左子树叶子结点数
11.  
    count2=Leaves(t->rchild);//右子树叶子结点数
12.  
    return count1 count2;//返回叶子结点数
13.  
    }
14.  
    }

完整带码如下：

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
   #include<malloc.h>
4.  
   #define MAX 20
5.  
   //二叉链表结点定义
6.  
   typedef struct BTNode
7.  
   {
8.  
   char data;
9.  
   struct BTNode *lchild;
10.  
    struct BTNode *rchild;
11.  
    }*BiTree;
12.  
     
13.  
    void createBiTree(BiTree *t)
14.  
    {
15.  
    //此处补充代码，完成以先序遍历方式建立二叉树
16.  
    char s;
17.  
    BiTree q;
18.  
    s=getchar();
19.  
    getchar();
20.  
    if(s=='#')
21.  
    {
22.  
    *t=NULL;
23.  
    return;
24.  
    }
25.  
    q=(BiTree)malloc(sizeof(struct BTNode));
26.  
    q->data=s;
27.  
    *t=q;
28.  
    createBiTree(&q->lchild);
29.  
    createBiTree(&q->rchild);
30.  
    }
31.  
    int Leaves(BiTree t)
32.  
    {
33.  
    //此处补充代码，统计二叉树中叶子结点数
34.  
    int count1,count2;
35.  
    if(t==NULL)return 0; //数空
36.  
    else
37.  
    if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点
38.  
    else
39.  
    {
40.  
    count1=Leaves(t->lchild);//左子树叶子结点数
41.  
    count2=Leaves(t->rchild);//右子树叶子结点数
42.  
    return count1 count2;//返回叶子结点数
43.  
    }
44.  
    }
45.  
     
46.  
    int depth(BiTree t)
47.  
    {
48.  
    //此处补充代码，求取二叉树的深度
49.  
    int hl,hr;
50.  
    if(t==NULL)return 0; //若数为空则返回0
51.  
    else
52.  
    {
53.  
    hl=depth(t->lchild); //递归求左子树的深度
54.  
    hr=depth(t->rchild); //递归求右子树的深度
55.  
    if(hl>hr)return (hl 1);
56.  
    else return (hr 1);
57.  
    }
58.  
    }
59.  
    int main()
60.  
    {
61.  
    //此处补充代码，按要求输出二叉树的叶子结点数和深度
62.  
    BiTree p;
63.  
    createBiTree(&p);
64.  
    printf("Leaves:%d\n",Leaves(p));
65.  
    printf("Depth:%d\n",depth(p));
66.  
    return 0;
67.  
    }

运行结果如下：

这篇好文章是转载于：学新通技术网