首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2018-09-11
28
问题
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
选项
A、n-1
B、n
C、n+1
D、n+2
答案
C
解析
首先,对于一棵树来讲,每个非终端结点(除了树的根结点)转换成二叉树后都对应一个无右孩子的结点,因为一个非终端结点至少有一个孩子结点,其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点?因为根结点比较特殊,树转换成二叉树之后,根结点本身也将会没有右孩子。所以对于一棵具有n个非终端结点的树来讲,将其转换成二叉树之后,二叉树中无右孩子的结点个数为n+1个。其实,此时已经可以选出答案了,因为一棵树也可以算是一个森林。
如果一个森林有多棵树(假设有x棵),我们先把所有树的根结点拿出来。除根结点之外的非终端结点(n-x个)转换成二叉树之后都是对应一个无右孩子的结点,可得到n-x个无右孩子的结点。但是,x个根结点是不足就对应2x个无右孩子的结点?显然不是,因为下一棵数将会成为上一棵树根结点的右孩子(见图5-3),所以只有森林的最后一棵树的根结点才会变成无右孩子的结点,故x个根结点将会得到x+1个无右孩子的根结点,所以一共可以得到n-x+(x+1)=n+1个无右孩子的根结点。
从图5-3可以看出,三棵树的根结点A、E、G转换成二叉树之后,只有最后一棵树的根结点G是没有右孩子的。
综上分析,二叉树中无右孩子的结点个数为n+1个,故选C选项。
转载请注明原文地址:https://kaotiyun.com/show/6qRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
明代中叶开始,松江地区“合郡男妇,皆以做袜为生,从店中给筹取值”。对此理解错误的是()。
土地革命战争时期,中国社会最基本的政治特征是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
第一次国共合作采取了共产党员以个人身份加入国民党的党内合作方式,最早提出这种方式的是()。
清政府被迫签订丧权辱国的《辛丑条约》后,彻底沦为“洋人的朝廷”。最能印证这一说法的是,清政府()
下列选项中,不是由晁错提出的是()。
1908年安庆新军起义是由()领导的。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
某计算机的主存地址空间大小为256MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下:假定int类型数据用32位补码表示,程序
随机试题
患者,男性,27岁。被蛇咬伤后6小时,四肢无力、呼吸困难2小时。查体:神志清,全身无出血,呼吸浅弱,四肢肌力1级。实验室检查:pH7.250,PaO245mmHg,PaCO255mmHg。下列急救措施中错误的是
促进胰岛素分泌的药物是
A.丘墟B.悬钟C.外丘D.足临泣E.足窍阴
有一建筑高度在249m具有办公、购物、娱乐、休闲及旅馆等多种服务功能的民用建筑,地下3层,裙楼5层,地上共计60层,内设有地下影院、地下商场、游泳馆、娱乐场所及自备发电机房等设备、设施。有设置在六层以上的会议厅,可停放98辆汽车的地下复式汽车库。请就该建筑
某投标人中标后,招标人要求其压低报价10%,否则不签合同。于是双方先按照中标人的投标报价签订了甲合同并备案。接着,双方又根据施工单位同意压价后的价格签字订了乙合同。后来,双方因工程款结算产生纠纷。关于工程款结算的合同依据,下列表述正确的是()。
下列说法正确的有( )。
以高难度、高速度、理论知识起主导作用、理解学习过程、使所有学生包括差生都得到一般发展为主要原则的教育学理论被称为()。
已知数列{an}是等差数列,其前n项和为Sn,若a3=7—a2,则S4=()
A、 B、 C、 A
A、Heissearchingforanewjob.B、Hehateslivingattheguesthouse.C、Hewantstogetmoresleep.D、Heisgoingtoopenarest
最新回复
(
0
)