PTA 二叉树求深度和叶子数(20 分)

二叉树求深度和叶子数(20 分)

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

函数接口定义:

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

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

裁判测试程序样例:

//头文件包含
#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;

//先序创建二叉树各结点
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 3 0 0 5 7 0 0 0

输出样例:

3 2
int GetDepthOfBiTree ( BiTree T)
{
    if(T==NULL) return 0;
    else return 1+(GetDepthOfBiTree(T->lchild)>GetDepthOfBiTree(T->rchild)?GetDepthOfBiTree(T->lchild):GetDepthOfBiTree(T->rchild));
}
int LeafCount(BiTree T)
{
    if(T==NULL) return 0;
    if(T!=NULL)
    {
        if(T->lchild==NULL&&T->rchild==NULL) return 1;
        else return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏乐沙弥的世界

SQL 基础--> ROLLUP与CUBE运算符实现数据汇总

--=============================================

963
来自专栏韦弦的微信小程序

Swift 加一 - LeetCode

语文能力捉急啊,看了半天没看懂。。。然后去找了英文原题(我实在LeetCode中文网做的题),英文描述如下:

703
来自专栏数据结构与算法

差分约束系统个人理解

今天接触到一种很玄幻的东西: 差分约束 个人的理解:差分约束就是给定一些限制条件,求出满足条件的最优解,或者判断条件是否成立 做法/思路: 1.首先根据题目的条...

3366
来自专栏有趣的Python

6-玩转数据结构-二分搜索树

电脑中的文件夹就是一种树结构,计算机中让人们使用的存储结构来源于生活。图书馆分区,分类,分子类。

2272
来自专栏菩提树下的杨过

无限级分类(非递归算法/存储过程版/GUID主键)完整数据库示例_(1)表结构

无限分类是一个老生常谈的话题了,网上有很多解决方案,可以分成二个流派,一种利用递归,一种利用非递归(当然需要其它一些辅助手段判断节点层次),但核心表结构都差不多...

1856
来自专栏熊二哥

那些年我们写过的T-SQL(中篇)

中篇的重点在于,在复杂情况下使用表表达式的查询,尤其是公用表表达式(CTE),也就是非常方便的WITH AS XXX的应用,在SQL代码,这种方式至少可以提高一...

1697
来自专栏HansBug's Lab

1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

2815
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

3635
来自专栏小樱的经验随笔

洛谷 P1972 [SDOI2009]HH的项链【莫队算法学习】

P1972 [SDOI2009]HH的项链 题目背景 无 题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他...

2366
来自专栏ACM算法日常

UVA10305 | 拓扑排序

John has n tasks to do. Unfortunately, the tasks are not independent and the exe...

652

扫码关注云+社区