首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2014-04-17
51
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
美国总统提出“十四点原则”的实际目的是()
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
我国第一部系统的史学理论著作是()。
我国第一部系统的史学理论著作是()。
下列选项中,控制了西域政权的是()
苏俄实施新经济政策的根本目的是()。
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
西南军阀跟随孙中山拥护护法运动的目的是()。
决定把苏联由农业国变成工业国的主要目的是()
随机试题
在绘制网络图时,应用较多的方法是【】
体层摄影中,X线曝光期间连杆摆过的角度称为
轻刺激能唤醒,醒后能进行简短而正确的交谈,见于下列哪种意识障碍
A、肾皮质B、肾髓质C、肾间质D、肾盂E、肾盏血行感染引起的急性肾盂肾炎,细菌最先侵犯
已知图中所示的三根弹簧的劲度系数分别为K1,K2,K3,振体的质量为m,则此系统沿铅垂方向振动的固有频率为( )。
金属材料物理特性随焊接温度的变化是影响焊接应力与变形的主要因素,而材料的()随温度的变化是决定焊接热应力,应变的重要物理特性。
韩国人受西方文化影响,接受礼品要当面打开。()
儿童的心理障碍更多以()为主。
不愿提高政府债务上限的共和党众议员和参议员将____。他们在____具有可怕后果的政策,而最终的结果将与他们声称所要的截然相反,因为违约将立刻让政府的重要性增加而不是减少。依次填入画横线部分最恰当的一项是()。
菲利普·莫里斯发行一种半年付息的债券,具有如下特性:利率为8%,收益率为8%,期限为15年,麦考利久期为10年。(1)利用上述信息,计算调整后的久期。(2)解释为什么调整后的久期是计算债券利率敏感性的较好方法。(3)确定调整后的持有
最新回复
(
0
)