计算二叉树的深度和叶子结点数(递归算法实现)
2021/12/4 14:17:11
本文主要是介绍计算二叉树的深度和叶子结点数(递归算法实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【问题描述】
计算二叉树的深度和叶子结点数
【输入形式】
输入二叉树的先序遍历序列建立二叉树。
【输出形式】
输出二叉树的叶子结点数和深度。
【样例输入】
A
B
C
#
#
#
#
【样例输出】
Leaves:1
Depth:3
求给定二叉树的深度:
二叉树的深度就是二叉树中结点的最大层次。如果二叉树是空树,则深度为0;否则,分别求二叉树根左子树和右子树的深度,取其中最大值加一就是该 二叉树的最大深度。
递归计算公式为:Depth(T)={0;当T==NULL; }
{max(Depth(T->lchild),Depth(T->rchild))+1;当T!=NULL;}
如下:
int depth(BiTree t) { //此处补充代码,求取二叉树的深度 int hl,hr; if(t==NULL)return 0; //若数为空则返回0 else { hl=depth(t->lchild); //递归求左子树的深度 hr=depth(t->rchild); //递归求右子树的深度 if(hl>hr)return (hl+1); else return (hr+1); } }
求叶子结点数也可以通过递归的方法进行统计。
方法如下:
int Leaves(BiTree t) { //此处补充代码,统计二叉树中叶子结点数 int count1,count2; if(t==NULL)return 0; //数空 else if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点 else { count1=Leaves(t->lchild);//左子树叶子结点数 count2=Leaves(t->rchild);//右子树叶子结点数 return count1+count2;//返回叶子结点数 } }
完整带码如下:
#include <stdio.h> #include <stdlib.h> #include<malloc.h> #define MAX 20 //二叉链表结点定义 typedef struct BTNode { char data; struct BTNode *lchild; struct BTNode *rchild; }*BiTree; void createBiTree(BiTree *t) { //此处补充代码,完成以先序遍历方式建立二叉树 char s; BiTree q; s=getchar(); getchar(); if(s=='#') { *t=NULL; return; } q=(BiTree)malloc(sizeof(struct BTNode)); q->data=s; *t=q; createBiTree(&q->lchild); createBiTree(&q->rchild); } /* void PreOrder(BiTree p) { //此处补充代码,完成二叉树的先序遍历 if(p!=NULL) { printf("%c",p->data); PreOrder(p->lchild); PreOrder(p->rchild); } } void InOrder(BiTree p) { //此处补充代码,完成二叉树的中序遍历 if(p!=NULL) { InOrder(p->lchild); printf("%c",p->data); InOrder(p->rchild); } } void PostOrder(BiTree p) { //此处补充代码,完成二叉树的后序遍历 if(p!=NULL) { PostOrder(p->lchild); PostOrder(p->rchild); printf("%c",p->data); } } */ int Leaves(BiTree t) { //此处补充代码,统计二叉树中叶子结点数 int count1,count2; if(t==NULL)return 0; //数空 else if(t->lchild==NULL&&t->rchild==NULL)return 1;//为叶子结点 else { count1=Leaves(t->lchild);//左子树叶子结点数 count2=Leaves(t->rchild);//右子树叶子结点数 return count1+count2;//返回叶子结点数 } } int depth(BiTree t) { //此处补充代码,求取二叉树的深度 int hl,hr; if(t==NULL)return 0; //若数为空则返回0 else { hl=depth(t->lchild); //递归求左子树的深度 hr=depth(t->rchild); //递归求右子树的深度 if(hl>hr)return (hl+1); else return (hr+1); } } int main() { //此处补充代码,按要求输出二叉树的叶子结点数和深度 BiTree p; createBiTree(&p); printf("Leaves:%d\n",Leaves(p)); printf("Depth:%d\n",depth(p)); return 0; }
运行结果如下:
这篇关于计算二叉树的深度和叶子结点数(递归算法实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南