首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2014-04-17
50
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
以下古代文件起到了限制王权作用的是()。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
《三家村札记》是由()三位作家共同完成的。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
葡萄牙、西班牙最早走上殖民征服道路,从政治上来说是由于()
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
随机试题
肾小管分泌的过程是
皮肤病最应忌的食物是
采用工料单价法编制单位工程预算时,在进行工料分析后紧接着的下一个步骤是()。【2015年真题】
【光大银行】2007出现的次贷危机大致经历的阶段有()
由非政府的民间金融组织确定的利率属于()。
2011年5月,甲、乙、丙合开了一间酒吧,甲以现金10万元出资,乙以其所有的房屋出资,丙以担任调酒师工作的劳务出资。2012年12月,酒吧欠酒厂5万元贷款。后甲因与其他合伙发生矛盾,于2013年2月退伙。上述债务应当()。
对下列农业知识的掌握有误的一项是()。
按照中国刑法规定,在我国领域外犯罪,不论罪行轻重,法定刑高低,都适用我国刑法的中国公民是()。
ItwasabadsignifsubtleshiftinthefarNorthAtlantic.For30years,watersoffsouthernGreenlandandIcelandhadbeengr
FrauundHerrMüllerwohneninMünchen,aber______KinderwohneninBonn.
最新回复
(
0
)