首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
在一棵二叉树中,度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中,如果共有200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
在一棵二叉树中,度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中,如果共有200个结点,则能判断出叶结点的个数吗?如果能,请指出会有多少个叶结点,多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
admin
2010-04-24
57
问题
在一棵二叉树中,度为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
数据结构
理工类
相关试题推荐
在1979年以前,ARPANET一直使用距离矢量路由算法,之后则被替换为()
在因特网中被广泛使用的_______协议用到了动态路由选择算法中的链路状态路由算法。
试述目前我国主要采用的货币政策的中介指标与操作指标。
下列有关现金漏损率的命题正确的是
设有指针head指向不带表头结点的单链表,用next表示结点的一个链域,指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中,使之成为第一个结点,则所需的操作为“p→next=head;”和“_______”。
如下图所示,给出表达式树的前序遍历序列、中序遍历序列和后序遍历序列。
画出一棵后序遍历序列与中序遍历序列相同的二叉树。
二叉排序树根结点的左子树中所有结点关键字值_________右子树中所有结点的关键字值。
已知用数组sq[50]存放循环队列的元素,且头指针和尾指针分别为19和2,则该队列的当前长度为_______。
随机试题
Whenhethoughtofthepast,mygrandfatherwouldsometimesshowusphotographsofhimselfatschool.Theywerebrownandfaded,
A.有头疽B.附骨疽C.锁喉痈D.瘰疬E.以上都不是
特殊人群高血压的治疗A、α-受体阻断剂(α-RB)B、β-受体阻断剂(β-RB)C、噻嗪类利尿药D、醛固酮受体拮抗剂E、血管紧张素转换酶抑制剂(ACEI)脑血管病病人宜选用的药物是
下列各项中,有关汇票与支票相互区别的表述中正确的有()。
健康保险所承保的疾病风险的特点有()
王某按照某银行支行的业务印章自行制作了一个业务印章,并印制了空白存单,然后制作了一张50万元的银行存单,并以此从另一家银行获得抵押贷款50万元。根据《刑法》的有关规定,有关王某的行为,下列说法正确的有()。
立国之初,明朝统治者就将发展教育事业放在重要地位,于是确立了“______”的文教政策。
堆是一种数据结构,(36)是堆。
Weneedonehundredmoresignaturesbeforewetakethe______tothegovernor.
TheriseandfallofvacationsTheriseTopvacationtime:AugustPaidvacationisa【D1】______.Theappearanceoftheword"vaca
最新回复
(
0
)