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面试题:18.二叉树的镜像

Step1.先序遍历原二叉树的每个节点,如果遍历到的结点有子结点,就交换它的两个子结点。

9710
来自专栏深度学习与计算机视觉

算法-重建二叉树

题目: 输入某二叉树的前序遍历与中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字,前序遍历序列为{},中序遍历序列为{},则重...

202100
来自专栏恰童鞋骚年

剑指Offer面试题:17.树的子结构

  为了方便测试,这里封装了一个设置指定根节点的左孩子和右孩子节点的方法:SetSubTreeNode

11720
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9920
来自专栏深度学习与计算机视觉

数据结构-二叉树遍历总结

二叉树结构 二叉树是一种特殊的树,每个父结点最多只能用有两个子结点。 ? 在树中,按照结点的“继承”关系可以分为父结点和子结点; 按照结点的位置...

20950
来自专栏恰童鞋骚年

剑指Offer面试题:25.二叉搜索树与双向链表

  首先,我们知道:在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。

12710
来自专栏机器学习实践二三事

二叉树的建立和各种遍历(java版)

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序 ->建树 假设现在有个二叉树,如下: ? 此时遍历顺序是: ...

33660
来自专栏猿人谷

树的子结构

题目:输入两棵二叉树A和B,判断B是不是A的子结构。 二叉树结点的定义如下: struct BinaryTreeNode { int ...

21280
来自专栏LeetCode

LeetCode <dfs>105&106 Construct Binary Tree

Given preorder and inorder traversal of a tree, construct the binary tree.

16860
来自专栏尾尾部落

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

链接:https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorde...

12120

扫码关注云+社区

领取腾讯云代金券