首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2014-04-17
27
问题
设一棵二叉树是由森林转换而来的,若森林中有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个(),经常派官员监察地方官吏。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
在19世纪60年代到90年代,洋务派兴办洋务事业的主要目的是()。
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
西南军阀跟随孙中山拥护护法运动的目的是()。
西南军阀跟随孙中山拥护护法运动的目的是()。
中国共产党召开七届二中全会的主要目的是()。
美国主张建立国际联盟的主要目的是()。
随机试题
心电图检查A.肺性P波B.肢导低电压C.右束支传导阻滞D.V1、V2R/S>1E.V1、V2ST—T改变右心室肥大的心电图表现
属于淋巴细胞白血病特点的是
皮下斑点隐隐稀少,色淡红,压之不退,伴诸虚症状,此为皮疹高出皮肤,时现时隐,搔之连片,此为
男性,5岁,右腹股沟可复性肿物1年。下列哪项手术方法最适宜
非对称信息,是指某些行为人拥有另一些行为人不拥有的信息。根据上述定义,下列属于非对称信息的是:
弯弯的森林小道上,守林人停下来,把我领到一棵参天的古树边,用深沉的眼光在告诉我什么,于是,我抬起头。我突然惊讶地发现原来这是一棵刚刚遭到雷火劈伤的古树,______。那些冷冷的光秃秃的枝桠伸向天空,好像在寻找着什么……填入上面语段中空白处的句子,与
文字资料2008年全年完成邮电业务总量23841亿元,比上年增长20.7%。其中,邮政业务总量1402亿元,增长15.5%;电信业务总量22440亿元,增长21.0%。全年减少局用交换机156万门,总容量5.1亿门。年末全国固定及移动电话用户总
新闻播音
资本一帝国主义列强通过军事侵略和不平等条约对中国进行政治控制,表现在
A、Whentheyfailtomakecompromisesindisputes.B、Whentheyneedtimetorest.C、Whentheywouldliketorecallgoodtimes.D、
最新回复
(
0
)