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

admin2010-04-24 88

问题在一棵二叉树中，度为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://www.kaotiyun.com/show/rgAx777K

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

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

数据结构

理工类

不属于TCP／IP协议层次的互联层能够提供的服务是()

办公自动化的核心是______，其所提供的主要通信手段为数据／声音综合服务、可视会议服务和电子邮件服务。

使每个网络节点轮流获得信道的使用权，没有数据要发送的节点将使用权传给下一节点的控制访问方法是()

在HDLC的常用操作方式中，________对采用轮询方式的多站链路来说是必不可少的。

________提供在串行通信线路上封装IP分组的简单方法，用以远程用户通过电话线和MODEM能方便地接入TCP／IP网络。()

金融期权按行权时间的不同来划分，可以分为_、___。

下列关于货币需求理论的说法正确的是()

有甲、乙两种货物，甲货物每件重5kg，体积为0．001m3，乙货物每件重10kg，体积为0．004m3．货车的载重量为15t，容量为5m3，求最佳配装方案．

已知无向图G的邻接矩阵如图C一5所示。请画出该无向图，并写出按深度优先搜索时的访问序列。

设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的_______。

部分激动药的特点为

下列关于价值网模型核心理念的描述错误的是()。

设λ1，λ2是矩阵A的两个不同的特征值，对应的特征向量分别为α1，α2，则α1，A(α1+α2)线性无关的充分必要条件是()。

两列对开的列车相遇，第一列车的速度为12米／秒，第二列车的速度为14米／秒，第二列车上的一旅客发现第一列车从旁边开过的时间为5秒，则第一列车的车长为多少米?()

大学毕业生在求职时，不仅在简历中写下了自己的学习成绩和实习经历，还把网络游戏的成绩和开网店的经历都写到了简历里，这一做法得到了部分用人单位的青睐。对此，你怎么看?

在TCP/IP体系结构中，ICMP属于(53)。

(1)modil．prg程序文件中SQLSELECT语句的功能是查询哪些零件（零件名称）目前用于三个项目，并将结果按升序存入文本文件results．txt。给出的SQLSELECT语句中在第1、3、5行各有一处错误，请改正并运行程序（不可以增、删语句或

由若干零件组成的、具有一定功能的部分为系统的部件，而零件可用于不同的部件，则实体部件和实体零件之间的联系是()

数据结构

理工类

不属于TCP／IP协议层次的互联层能够提供的服务是()

办公自动化的核心是______，其所提供的主要通信手段为数据／声音综合服务、可视会议服务和电子邮件服务。

使每个网络节点轮流获得信道的使用权，没有数据要发送的节点将使用权传给下一节点的控制访问方法是()

在HDLC的常用操作方式中，________对采用轮询方式的多站链路来说是必不可少的。

________提供在串行通信线路上封装IP分组的简单方法，用以远程用户通过电话线和MODEM能方便地接入TCP／IP网络。()

金融期权按行权时间的不同来划分，可以分为_________、___________。

下列关于货币需求理论的说法正确的是()

有甲、乙两种货物，甲货物每件重5kg，体积为0．001m3，乙货物每件重10kg，体积为0．004m3．货车的载重量为15t，容量为5m3，求最佳配装方案．

已知无向图G的邻接矩阵如图C一5所示。请画出该无向图，并写出按深度优先搜索时的访问序列。

设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的_______。

部分激动药的特点为

下列关于价值网模型核心理念的描述错误的是()。

设λ1，λ2是矩阵A的两个不同的特征值，对应的特征向量分别为α1，α2，则α1，A(α1+α2)线性无关的充分必要条件是()。

两列对开的列车相遇，第一列车的速度为12米／秒，第二列车的速度为14米／秒，第二列车上的一旅客发现第一列车从旁边开过的时间为5秒，则第一列车的车长为多少米?()

大学毕业生在求职时，不仅在简历中写下了自己的学习成绩和实习经历，还把网络游戏的成绩和开网店的经历都写到了简历里，这一做法得到了部分用人单位的青睐。对此，你怎么看?

在TCP/IP体系结构中，ICMP属于(53)。

(1)modil．prg程序文件中SQLSELECT语句的功能是查询哪些零件（零件名称）目前用于三个项目，并将结果按升序存入文本文件results．txt。给出的SQLSELECT语句中在第1、3、5行各有一处错误，请改正并运行程序（不可以增、删语句或

由若干零件组成的、具有一定功能的部分为系统的部件，而零件可用于不同的部件，则实体部件和实体零件之间的联系是()

金融期权按行权时间的不同来划分，可以分为_、___。