首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2014-04-17
49
问题
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
选项
A、n一1
B、n
C、n+1
D、n+2
答案
C
解析
首先,对于一棵树来讲,每个非终端结点(除了树的根结点)转换成二叉树后都对应一个无右孩子的结点,因为一个非终端结点至少有一个孩子结点,其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点?因为根结点比较特殊,树转换成二叉树之后,根结点本身也将会没有右孩子。所以对于一棵具有n个非终端结点的树来讲,将其转换成二叉树之后,二叉树中无右孩子的结点个数为n+1个。其实,此时已经可以选出答案了,因为一棵树也可以算是一个森林。 如果一个森林有多棵树(假设有x棵),先把所有树的根结点拿出来。除根结点之外的非终端结点(n—x个)转换成二叉树之后都是对应一个无右孩子的结点,可得到n—x个无右孩子的结点。但是,x个根结点是不是就对应2x个无右孩子的结点?显然不是,因为下一棵数将会成为上一棵树根结点的右孩子(见图5-2),所以只有森林的最后一棵树的根结点才会变成无右孩子的结点,故x个根结点将会得到x+1个无右孩子的根结点,所以一共可以得到n—x+(x+1)=n+1个无右孩子的根结点。
从图5-2可以看出,3棵树的根结点A、E、G转换成二叉树之后,只有最后一棵树的根结点G是没有右孩子的。 综上分析,二叉树中无右孩子的结点个数为n+1个,故选C选项。
解题技巧:使用特殊值代入法,如图5-3所示。
从图5—3中可以很直观地看出无右孩子结点比非终端结点多1。
转载请注明原文地址:https://kaotiyun.com/show/fexi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
周王室的两大官僚系统是()。
美国总统提出“十四点原则”的实际目的是()
系统阐明社会主义初级阶段理论是在()。
下列不属于维也纳会议召开的目的的是()。
西汉时期,张骞第一次出使西域的主要目的是()
我国第一部系统的史学理论著作是()。
葡萄牙、西班牙最早走上殖民征服道路,从政治上来说是由于()
16世纪英国国王推行宗教改革的根本目的是()
美国主张建立国际联盟的主要目的是()。
决定把苏联由农业国变成工业国的主要目的是()
随机试题
A、脐疝B、腹股沟斜疝C、股疝D、腹股沟直疝E、切口疝患者男性,46岁,发现右腹股沟肿块2年,术中发现腹壁下动脉在疝囊颈外侧,应考虑为
患者女,44岁,左侧鼻塞,多清涕2年余,不伴鼻痒及打喷嚏,鼻腔检查见鼻中隔明显左偏,左中鼻道少许分泌物。鼻窦CT示:鼻中隔左偏,左侧上颌窦黏膜稍增厚,最适当的治疗是
下列肋骨中可称为假肋的是
孕妇,36岁。妊娠10周,休息时仍感胸闷、气急。查体:脉搏120次/分,呼吸22次/分,心界向左侧扩大,心尖区有Ⅱ级收缩期杂音,肺底有湿啰音,应采取的处理措施是
对工程项目进行全面管理的中心的是()
在民事诉讼程序中,下列情形可以缺席判决的有()。
在销售与收款循环的审计中,丙注册会计师确定的审计目标是“所有销售交易均已登记入账”,针对这一审计目标,下列说法中错误的是()。在生产与存货循环的审计中,丙注册会计师实施监盘程序,无法实现的审计目标是()。
一般资料:求助者,女性,35岁,已婚,工厂普通工人。案例介绍:有一次求助者上班时眼看就要迟到,就急匆匆地往车间里跑,不小心与公司男领导撞了个满怀,同事们顿时都笑起来,还有人吹起口哨,大家事后还总拿他们开玩笑。以后求助者每次去车间都会紧张,觉得同事
水仙(清)李渔水仙一花,予之命也。予有四命,各司一时:春以水仙兰花为命;夏以莲为命;秋以秋海棠为命;冬以腊梅为命。无此四花,是无命也。一季夺予一花,是夺予一季之命也。水仙以秣陵①为最,
[*]
最新回复
(
0
)