首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
在一棵二叉树中,度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中,如果共有200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
在一棵二叉树中,度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中,如果共有200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
admin
2010-04-24
68
问题
在一棵二叉树中,度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中,如果共有200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
选项
答案
在一棵二叉树中,度数为0的结点(叶结点)的个数总是比度为2的结点的个数多1。根据完全二叉树的定义:若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干住置上,则我们可以得出这样一个结论:在一棵完全二叉树上,或者没有度为1的结点。则根据以上分析,我们可以这样计算此题:设度数为2的结点有n个,则必有n+1个度为0的结点,即度数为2和度数为0的结点数之和为2n+1(是奇数),于是得出,如果一棵完全二叉树的结点总数为奇数,则此树中必然不存在度为1的结点,若完全二叉树中结点总数为偶数,则必然有1个度为1的结点存在,于是若完全二叉树中有200个结点,就必有100个对结点,99个度数为2的结点,12个度数为1的结点,如果二叉树中有201个结点,则必有101个叶结点,100个度数为2的结点,没有度数为1的结点。
解析
转载请注明原文地址:https://kaotiyun.com/show/rgAx777K
本试题收录于:
数据结构题库理工类分类
0
数据结构
理工类
相关试题推荐
有一个100Mbit/s的令牌环网络,令牌环行时间是120μs,每个主机在每次得到令牌后可以发送1000字节的分组,发送完成后立即释放令牌。试求出任意一台主机可以取得的最大吞吐率。
在1979年以前,ARPANET一直使用距离矢量路由算法,之后则被替换为()
下列不属于HDLC常用的操作方式的是()
因特网的域名空间是一种层次型的_______。()
下列IP地址中错误的是()
以下各因素对汇率变动有长期影响,除了()
处理货币政策目标冲突的途径有
金融期权按行权时间的不同来划分,可以分为()
设以二叉链表为二叉树的存储结构,结点的结构如下:lehilddatarchild其中data域为整数,试设计一个算法voidchange(bitreptrr):若结点左孩子的data域的值大于右孩子的data域的值,则交
若用后根遍历法遍历图C-2所示的二叉树,其输出序列为_______。
随机试题
奥运会的格言是“更快、更高、更强”。请结合这一格言,自拟题目。要求:A.自定立意,可写成记叙文、议论文。B.不少于800字。C.字迹工整,卷面整洁。
小儿腹泻脱水,在脱水纠正后出现抽搐,最常见的原因是
印制规范包括()要求。
根据《会计人员继续教育暂行规定》,具有初级会计专业技术资格的会计人员每年接受继续教育的培训时间最少应为()。
下列各项中,属于企业所有者权益组成部分的有()。
Whathealthproblemsdomanyelderlyhave?MaggieKuhntravelsacrosstheUnitedStatesinorderto______elders.
A、 B、 C、 D、 D
A、Yellow.B、Green.C、White.A本题询问丽莉的衣服是什么颜色的。女士说:TheblueoneisLucy’s,andtheyellowoneisLily’s.可知答案为[A]Yellow。
MESOLITHICCOMPLEXITYINSCANDINAVIA(1)TheEuropeanMesolithic(roughlytheperiodfrom8000B.C.to2700B.C.)testifiest
A、Hefounditmoreprofitable.B、Hewantedtobehisownboss.C、Hedidn’twanttostartfromscratch.D、Hedidn’twanttobein
最新回复
(
0
)