首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2014-04-17
70
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
周王室的两大官僚系统是()。
美国总统提出“十四点原则”的实际目的是()
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
我国第一部系统的史学理论著作是()。
为了加强对地方的控制,唐太宗根据山川形势,把全国划分成10个(),经常派官员监察地方官吏。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
联共(布)“十五大”以后,新经济政策被逐步取消,根本上是由于()。
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
中国共产党召开七届二中全会的主要目的是()。
随机试题
A.白果B.枇杷叶C.桑白皮D.半夏E.瓜蒌哪项中药是湿痰痰多、心下痞首选的
一贫血患者,测得MCV:75fl,MCH24pg,MCHC31%,网织红细胞0.011,口服硫酸亚铁0.3/次,每日3次治疗一周,复查RBC、Hb未见明显改善,网织红细胞0.065,对此患者应采取
男性,62岁,咳嗽30年,近日咯大量脓痰,气憋,下肢水肿,本病最主要的治疗原则
根据《建设工程项目管理规范》(GB/T50326—2006),下列属于项目经理的职责的有()。
简述教学评价的功能与意义。
国内外政治环境以及国家的社会经济政策也是影响和决定生产力布局的主要因素之一。()
A.Iliterallycan’tstop.B.ButnowIdon’tneedtoworryanymore.C.You’reknownasthefirstbillionaireauthorhere.D.B
______不是算法必须具备的特性。
AccordingtoAustin,whichofthefollowingutterancescanberegardedasaperformative?
A、Itcouldhelppeopleofallagestoavoidcancer.B、Itwasmainlymeantforcancerpatients.C、Itmightappealmoretoviewers
最新回复
(
0
)