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

admin2010-04-24 71

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

数据结构

理工类

_______是用于在不可靠的因特网上提供可靠的、端到端的字节流通信的协议。

传输服务是通过建立连接的两个传输实体之间所采用的_______来实现的。

ATM网络支持面向连接的信元交换，数据信元交换之前必须建立________。()

简述ATM的工作方式。

在数据传输过程中，若接收方收到发送方送来的信息为10110011010，生成多项式为G(x)=x4+x3+1，请问接收方收到的数据是否正确?(请写出判断依据及推演过程)

股票投资分析中的基本面分析主要包括()

如图C-4所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。

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

若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是________。

判别循环队列空和满的方法有___、_和_____。

公安机关在要求人民检察院复议逮捕决定的时候，必须将被拘留的人立即释放。

有关脊髓空洞症，下述哪个是不正确的

下列关于外交、领事人员的行为的表述，哪些选项是正确的?

职业健康安全风险控制措施计划作为技术组织措施，主要内容包括职业健康安全技术措施、工业卫生技术措施、辅助房屋及设施和()。

关于建设工程超过合理使用年限后需要继续使用的说法，正确的是()。

根据有效银行监管的公正原则，监管部门不能根据商业银行的风险状况和风险管理能力对商业银行资本实行分类监管。()

旅游投诉一般应当采用书面形式，一式()份，并载明规定的内容。

在文件系统中，文件的逻辑块与存储介质上物理块存放顺序一致的物理结构是()。

RailwaysinBritainThesuccessofearlyrailways,suchasthelinesbetweenbigcities,/ledtoagreatincreaseinrailw

A、Inadepartmentstore.B、Inapostoffice.C、Inabank.D、Inagrocerystore.A

数据结构

理工类

_______是用于在不可靠的因特网上提供可靠的、端到端的字节流通信的协议。

传输服务是通过建立连接的两个传输实体之间所采用的_______来实现的。

ATM网络支持面向连接的信元交换，数据信元交换之前必须建立________。()

简述ATM的工作方式。

在数据传输过程中，若接收方收到发送方送来的信息为10110011010，生成多项式为G(x)=x4+x3+1，请问接收方收到的数据是否正确?(请写出判断依据及推演过程)

股票投资分析中的基本面分析主要包括()

如图C-4所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。

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

若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是________。

判别循环队列空和满的方法有_______、_______和_______。

公安机关在要求人民检察院复议逮捕决定的时候，必须将被拘留的人立即释放。

有关脊髓空洞症，下述哪个是不正确的

下列关于外交、领事人员的行为的表述，哪些选项是正确的?

职业健康安全风险控制措施计划作为技术组织措施，主要内容包括职业健康安全技术措施、工业卫生技术措施、辅助房屋及设施和()。

关于建设工程超过合理使用年限后需要继续使用的说法，正确的是()。

根据有效银行监管的公正原则，监管部门不能根据商业银行的风险状况和风险管理能力对商业银行资本实行分类监管。()

旅游投诉一般应当采用书面形式，一式()份，并载明规定的内容。

在文件系统中，文件的逻辑块与存储介质上物理块存放顺序一致的物理结构是()。

RailwaysinBritainThesuccessofearlyrailways,suchasthelinesbetweenbigcities,/ledtoagreatincreaseinrailw

A、Inadepartmentstore.B、Inapostoffice.C、Inabank.D、Inagrocerystore.A

判别循环队列空和满的方法有___、_和_____。