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 条评论
登录 后参与评论

相关文章

来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

732
来自专栏用户2442861的专栏

二叉树的非递归遍历

                                                            二叉树的非递归遍历

631
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】树篇

【本文目录】 树的定义 相关术语 用数组表示二叉树 用链表表示二叉树 节点的定义与方法 树的定义与方法 ---- 树的定义 树(tree)是包含n(n>0)个结...

2727
来自专栏Crossin的编程教室

【每周一坑】杨辉三角形

杨辉三角形,也称帕斯卡三角,其定义为:顶端是 1,视为(row0).第1行(row1)(1&1)两个1,这两个1是由他们上头左右两数之和 (不在三角形内的数视为...

2534
来自专栏好好学习吧

数据结构--双向循环链表

http://www.cnblogs.com/skywang12345/p/3561803.html

922
来自专栏深度学习思考者

Python学习(三) 八大排序算法的实现(上)

   本文Python实现了直接插入排序、基数排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、希尔排序。    上篇来介绍前四种排序方式:  ...

1818
来自专栏人工智能LeadAI

算法 | 数据结构常见的八大排序算法

01 前言 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下: ...

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

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

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

洛谷 P3386 【模板】二分图匹配 Dinic版

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

3169
来自专栏架构之路

并查集Union-find及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

2694

扫码关注云+社区