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

admin2010-04-24 27

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

数据结构

理工类

距离矢量路由算法最初是ARPNET使用的路由算法，也被用于Internet的_______协议。

在局域网操作系统中，_______功能可向用户提供电子邮件服务，也可提供数据的同步传输服务。()

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

为什么说中央银行票据的发行丰富了公开市场业务操作工具?

下面是60个大学生一个月生活费支出的调查数据：375，375，255，315，270，405，360，240，285，300，480，390，495，615，225435，525，450，225，390，300，285，375，425，600，405，

某玻璃厂要生产四种型号的瓶子，都要经过在甲设备上消毒之后，才能在乙设备上密封。每种瓶子在每台设备上所需的加工时间如表3。2所示。问如何安排这些瓶子的加工顺序，可使总的加工时间最短?

某厂用6种化工原料混合配制某工业材料，要求配制成的每份工业材料内含成分A不少于9单位/公斤，成分B不少于15单位/公斤，有关数据如表所示，问应如何建立该问题数学模型，既满足对A、B的质量要求，又使配制成本最低?

排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_______。

设有数据逻辑结构为：B=(K，R)K={k1，k2，…，k9}R={，，，，，，，，，，}画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点?

若对图中所示的二叉树进行中序线索化，则结点D的左右线索域的指针分别指向_______结点。

公民、法人或者其他组织对行政机关所给予的行政处罚，享有（）等权利。

古代文献中记载的_______，被认为是传说中五帝时代的“大学”。

中药处方的正文不包括

A．桃仁、丹皮、芒硝B．赤芍、丹皮、甘草C．大黄、芒硝、赤芍D．大黄、桃仁、甘草E．大黄、赤芍、丹皮桃核承气汤的组成中含有药物是

下面化合物在水中溶解度最大的是

网络图的费用优化是指寻求(　　)的过程。

关于砌体墙上留置临时施工洞口的说法，正确的是()。

个体心理发展遵循着颇为一致的规律，表现出与他人一致的共同性，但又表现出相对特殊性。这体现了个体心理发展的()。

有如下程序段：intx=12；doubley=3．141593；printf("％d％8．6f"，x，y)；其输出结果是

Heisa(n)______andwell-behavedchild,buthisparentsworryabouthimforhetalkstoolittle.(2005年春季电子科技大学考博试题)

数据结构

理工类

距离矢量路由算法最初是ARPNET使用的路由算法，也被用于Internet的_______协议。

在局域网操作系统中，_______功能可向用户提供电子邮件服务，也可提供数据的同步传输服务。()

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

为什么说中央银行票据的发行丰富了公开市场业务操作工具?

下面是60个大学生一个月生活费支出的调查数据：375，375，255，315，270，405，360，240，285，300，480，390，495，615，225435，525，450，225，390，300，285，375，425，600，405，

某玻璃厂要生产四种型号的瓶子，都要经过在甲设备上消毒之后，才能在乙设备上密封。每种瓶子在每台设备上所需的加工时间如表3。2所示。问如何安排这些瓶子的加工顺序，可使总的加工时间最短?

某厂用6种化工原料混合配制某工业材料，要求配制成的每份工业材料内含成分A不少于9单位/公斤，成分B不少于15单位/公斤，有关数据如表所示，问应如何建立该问题数学模型，既满足对A、B的质量要求，又使配制成本最低?

排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_______。

设有数据逻辑结构为：B=(K，R)K={k1，k2，…，k9}R={，，，，，，，，，，}画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点?

若对图中所示的二叉树进行中序线索化，则结点D的左右线索域的指针分别指向_______结点。

公民、法人或者其他组织对行政机关所给予的行政处罚，享有（）等权利。

古代文献中记载的_______，被认为是传说中五帝时代的“大学”。

中药处方的正文不包括

A．桃仁、丹皮、芒硝B．赤芍、丹皮、甘草C．大黄、芒硝、赤芍D．大黄、桃仁、甘草E．大黄、赤芍、丹皮桃核承气汤的组成中含有药物是

下面化合物在水中溶解度最大的是

网络图的费用优化是指寻求( )的过程。

关于砌体墙上留置临时施工洞口的说法，正确的是()。

个体心理发展遵循着颇为一致的规律，表现出与他人一致的共同性，但又表现出相对特殊性。这体现了个体心理发展的()。

有如下程序段：intx=12；doubley=3．141593；printf("％d％8．6f"，x，y)；其输出结果是

Heisa(n)______andwell-behavedchild,buthisparentsworryabouthimforhetalkstoolittle.(2005年春季电子科技大学考博试题)

网络图的费用优化是指寻求(　　)的过程。