PTA（树和二叉树）1-4 二叉树求深度和叶子数

1-4 二叉树求深度和叶子数

分数 3

作者 鲁法明

单位 浙江大学

编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构

函数接口定义：

1
2
int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);

其中 T是用户传入的参数，表示二叉树根节点的地址。函数须返回二叉树的深度（也称为高度）。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

//函数状态码定义
#define TRUE       1
#define FALSE      0
#define OK         1
#define ERROR      0
#define OVERFLOW   -1
#define INFEASIBLE -2
#define NULL  0
typedef int Status;

//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

//创建二叉树各结点，输入零代表创建空树
//采用递归的思想创建
//递归边界：空树如何创建呢：直接输入0；
//递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！

Status CreateBiTree(BiTree &T){
   TElemType e;
   scanf("%d",&e);
   if(e==0)T=NULL;
   else{
     T=(BiTree)malloc(sizeof(BiTNode));
     if(!T)exit(OVERFLOW);
     T->data=e;
     CreateBiTree(T->lchild);
     CreateBiTree(T->rchild);
   }
   return OK;  
}

//下面是需要实现的函数的声明
int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);
//下面是主函数
int main()
{
   BiTree T;
   int depth, numberOfLeaves;
   CreateBiTree(T);
   depth= GetDepthOfBiTree(T);
     numberOfLeaves=LeafCount(T);
   printf("%d %d\n",depth,numberOfLeaves);
}

/* 请在这里填写答案 */

输入样例：

1
1 3 0 0 5 7 0 0 0

输出样例：

1
3 2

答案

  • 一遍过，跟前面逻辑类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int GetDepthOfBiTree ( BiTree T) {
    int m, n;
    if (T == NULL) { // 如果是空树，直接退出
        return 0;
    } else {
        m = GetDepthOfBiTree(T->lchild); // 计算左子树的深度
        n = GetDepthOfBiTree(T->rchild); // 计算右子树的深度
        if (m > n) {
            return m + 1;
        }else {
            return n + 1;
        }
    }
}

int LeafCount(BiTree T) {
    // 如果是空树，直接退出
    if (T == NULL) {
        return 0;
    }
    // 度为0的结点
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    // 度为1的结点
    if ((T->lchild != NULL && T->rchild == NULL) || T->lchild == NULL && T->rchild != NULL) {
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
    // 是度为2的结点
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}