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

admin2010-04-24 89

问题在一棵二叉树中，度为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)

数据结构

理工类

IPV6将IP地址的长度增加到了_______，使地址空间增大了296倍。

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

IP数据报在传输过程中经分段后进行传输，在到达目的主机之前，分段后的IP数据报()

在网络层中，数据以______为单位进行传输。()

完成路径选择功能是在OSI模型的_______。()

银行信用的特点包括、_、银行信用可以独立于商品买卖活动、银行信用具有广泛的授信对象、银行信用可以满足存贷款人在数量和期限上的多样化需求。数量和期限上的多样化需求。

凯恩斯对货币需求理论的突出贡献在于他对货币需求动机的剖析在此基础上，把什么引入了货币需求函数?()

设有A，B，C三个人去完成I，Ⅱ，Ⅲ三项任务，要求每一个人只能完成一项任务，每项任务只由一个人完成，效益矩阵中相关数据由表6．10给出。问怎样把三项任务分派给三个人，使所得效益最高?

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是__、_和___。

树的后序遍历序列与其对应二叉树的_________遍历序列相同。

与西药利尿药联用，可减轻因应用西药利尿药而导致的口渴等副作用的是()。

评价化学毒物急性毒性大小最重要的参数是

咯血最常见于

遗传密码的摆动性是指

Influenzaiscausedbyavirusonepersonanotherindropletscoughedorsneezedintotheair.Itischaracterizedby

[A]apparent[B]automatic[C]Consequently[D]Decidedly[E]decline[F]delightful[G]enrollments[H]financial[I]intimate[J]junior[K]prof

数据结构

理工类

IPV6将IP地址的长度增加到了_______，使地址空间增大了296倍。

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

IP数据报在传输过程中经分段后进行传输，在到达目的主机之前，分段后的IP数据报()

在网络层中，数据以______为单位进行传输。()

完成路径选择功能是在OSI模型的_______。()

银行信用的特点包括__________、___________、银行信用可以独立于商品买卖活动、银行信用具有广泛的授信对象、银行信用可以满足存贷款人在数量和期限上的多样化需求。数量和期限上的多样化需求。

凯恩斯对货币需求理论的突出贡献在于他对货币需求动机的剖析在此基础上，把什么引入了货币需求函数?()

设有A，B，C三个人去完成I，Ⅱ，Ⅲ三项任务，要求每一个人只能完成一项任务，每项任务只由一个人完成，效益矩阵中相关数据由表6．10给出。问怎样把三项任务分派给三个人，使所得效益最高?

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是______、_________和_______。

树的后序遍历序列与其对应二叉树的_________遍历序列相同。

与西药利尿药联用，可减轻因应用西药利尿药而导致的口渴等副作用的是()。

评价化学毒物急性毒性大小最重要的参数是

咯血最常见于

遗传密码的摆动性是指

Influenzaiscausedbyavirus______oneperson______anotherindropletscoughedorsneezedintotheair.Itischaracterizedby

[A]apparent[B]automatic[C]Consequently[D]Decidedly[E]decline[F]delightful[G]enrollments[H]financial[I]intimate[J]junior[K]prof

银行信用的特点包括、_、银行信用可以独立于商品买卖活动、银行信用具有广泛的授信对象、银行信用可以满足存贷款人在数量和期限上的多样化需求。数量和期限上的多样化需求。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是__、_和___。

Influenzaiscausedbyavirusonepersonanotherindropletscoughedorsneezedintotheair.Itischaracterizedby