首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
专升本
在一棵二叉树中,度为零的结点个数为n0,度为2的结点个数为n2,则有n0__________。
在一棵二叉树中,度为零的结点个数为n0,度为2的结点个数为n2,则有n0__________。
admin
2014-08-29
52
问题
在一棵二叉树中,度为零的结点个数为n
0
,度为2的结点个数为n
2
,则有n
0
__________。
选项
答案
n2+1
解析
假设二叉树中度为1的结点个数为n1,结点总数为n。因为二叉树中任何结点的度最大不超过2,因此有:n=n0+n1+n2(1)从另一个角度看,我们来研究二叉树的分支数。对所有结点来说,除了根结点,任何其余结点都有一个分支进入(指向)。不妨设B(Branch)为二叉树的分支数,则有:B=n一1(分支数比结点数少1)(2)而分支是由度为1的结点和度为2的结点贡献的:每个度为1的结点贡献1个分支,每个度为2的结点贡献2个分支。则有:B=n1×1+n2×2=n1+2n2(3)由(2)、(3)得n=n1+2n2+1(4)由(1)、(4)得n0=n2+1由此得出结论:二叉树叶子结点个数总是比度为2的结点个数多1。
转载请注明原文地址:https://kaotiyun.com/show/SyvR777K
本试题收录于:
计算机科学与技术题库普高专升本分类
0
计算机科学与技术
普高专升本
相关试题推荐
医院可采取下列哪些方法来预防医院感染的发生()。
按系统组成的要素分人是()。
减少后张法中的磨擦损失的措施有_________和_________。
结构安全就意味着结构可靠。()
对两个不同频率的主振型,一个振型上的惯性力在另一个振型上的功()
一单自由度振动体系,由初始位移0.685cm,初始速度为零产生自由振动,振动一个周期后最大位移为0.50cm,体系的阻尼比为()
荷载的临界位置必然有一集中力作用在影响线顶点,若有一集中力作用在影响线顶点也必为一荷载临界位置。
栈是一种特殊的线性表,它允许在表的一端进行_______操作,栈中元素的进出原则为_______。
给定如下图所示的带权无向图G1。给出采用普里姆算法从顶点3出发构造最小生成树的过程。
随机试题
总的来说,文学传播的发展所经历的阶段包括【】
患儿,7岁。8月10日发病出现高热、头痛、呕吐1次,次日排稀便2次,精神不振,晚间开始抽搐、神志不清。体检:体温39.5℃,急性病容,脉充实有力,颈有抵抗,克氏征阳性,布氏征阳性,肌张力高,血白细胞15×109/L,粪镜检白细胞每高倍视野0~2个,脑脊液检
很少引起AIDS患者机会性感染的病原体是
下列各项中,不属于汇总记账凭证会计核算程序特点的有()。
下列各项说法中,不正确的是()。
已知复数集{zn}成等比数列,其首项和公比均为1-i,则z3=().
甲拥有一辆“福特”汽车,以10万元出让给乙,但是,双方同时约定,甲在购买到“丰田”汽车之后,再正式向乙交付“福特”汽车。甲、乙之间买卖“福特”汽车的合同是()的合同。
下列说法不正确的是()。
Wheredoourfavoritefoodscomefrom?Thetruthmay(31)you.Didyouknowcurry(咖喱)isn’tIndian?DidyouknowAmericanswe
Forthispart,youareallowed30minutestowriteacompositiononthetopic"MyIdealJob".Youshouldwriteinnolessthan1
最新回复
(
0
)