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

admin2010-04-24 29

问题在一棵二叉树中，度为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://jikaoti.com/ti/V2taFFFM

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

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

数据结构

理工类

_______攻击的主要目的是窃听和监视信息的传输并存储，攻击者只是想获得被传送的信息。()

为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为________。

按交换方式分类，计算机网络可以分为_______交换网、报文交换网、分组交换网三种。

处理货币政策目标冲突的途径有

用图解法求下列两个变量的线性规划问题：使目标函数f=3x+3y达到最大。

用匈牙利算法求解下述指派问题．效率矩阵如下：

分别写出图C-3中二叉树的先根、中根、后根遍历序列。

具有n个结点的完全二叉树，顺序存储在一维数组A[1…，z]中，设计算法将A中顺序存储变为二叉链表存储的二叉树。

对如下图所示的二叉排序树，给出删除关键字85后的二叉排序树。

在急性冠状动脉综合征后的下列哪种情况可单用氯吡格雷?

直径为d的实心圆轴受扭，在扭矩不变的情况下，为使扭转最大切应力减小一半，圆轴的直径应改为：

()是一种兼具资本金和债务资金特点的有价证券。

证券经营机构的作用主要体现在()几个方面。

在标准成本系统中，直接材料的价格标准是指预计下年度实际需要支付的材料市价。()

()对于领航相当于规则对于()

下列各组软件中，全部属于应用软件的是()。

A--skincareB--sunscreen/sunblockC--whiteningD--daycreamE--nigh

__________________(我对他能度过危机有信心),basedonhismanynarrowescapesinthepast.