在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?

admin2010-04-24 57

问题在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?

选项

答案在一棵二叉树中，度数为0的结点(叶结点)的个数总是比度为2的结点的个数多1。根据完全二叉树的定义：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干住置上，则我们可以得出这样一个结论：在一棵完全二叉树上，或者没有度为1的结点。则根据以上分析，我们可以这样计算此题：设度数为2的结点有n个，则必有n+1个度为0的结点，即度数为2和度数为0的结点数之和为2n+1(是奇数)，于是得出，如果一棵完全二叉树的结点总数为奇数，则此树中必然不存在度为1的结点，若完全二叉树中结点总数为偶数，则必然有1个度为1的结点存在，于是若完全二叉树中有200个结点，就必有100个对结点，99个度数为2的结点，12个度数为1的结点，如果二叉树中有201个结点，则必有101个叶结点，100个度数为2的结点，没有度数为1的结点。

解析

转载请注明原文地址:https://kaotiyun.com/show/rgAx777K

本试题收录于：数据结构题库理工类分类

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

数据结构

理工类

在1979年以前，ARPANET一直使用距离矢量路由算法，之后则被替换为()

在因特网中被广泛使用的_______协议用到了动态路由选择算法中的链路状态路由算法。

试述目前我国主要采用的货币政策的中介指标与操作指标。

下列有关现金漏损率的命题正确的是

设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“_______”。

如下图所示，给出表达式树的前序遍历序列、中序遍历序列和后序遍历序列。

画出一棵后序遍历序列与中序遍历序列相同的二叉树。

二叉排序树根结点的左子树中所有结点关键字值_________右子树中所有结点的关键字值。

已知用数组sq[50]存放循环队列的元素，且头指针和尾指针分别为19和2，则该队列的当前长度为_______。

Whenhethoughtofthepast,mygrandfatherwouldsometimesshowusphotographsofhimselfatschool.Theywerebrownandfaded,

A．有头疽B．附骨疽C．锁喉痈D．瘰疬E．以上都不是

特殊人群高血压的治疗A、α-受体阻断剂(α-RB)B、β-受体阻断剂(β-RB)C、噻嗪类利尿药D、醛固酮受体拮抗剂E、血管紧张素转换酶抑制剂(ACEI)脑血管病病人宜选用的药物是

下列各项中，有关汇票与支票相互区别的表述中正确的有()。

健康保险所承保的疾病风险的特点有()

王某按照某银行支行的业务印章自行制作了一个业务印章，并印制了空白存单，然后制作了一张50万元的银行存单，并以此从另一家银行获得抵押贷款50万元。根据《刑法》的有关规定，有关王某的行为，下列说法正确的有()。

立国之初，明朝统治者就将发展教育事业放在重要地位，于是确立了“______”的文教政策。

堆是一种数据结构，(36)是堆。

Weneedonehundredmoresignaturesbeforewetakethe______tothegovernor.

TheriseandfallofvacationsTheriseTopvacationtime:AugustPaidvacationisa【D1】______.Theappearanceoftheword"vaca