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

admin2010-04-24 69

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

数据结构

理工类

下列选项中不是传输层协议与数据链路层协议相似的地方的是()

信源以字节(8比特)为单位传输数据，若数据速率为B(bit／s)，对下列两种情况分别计算有效数据传输速率：(1)异步串行传输，无校验位、1位停止位；(2)同步串行传输，每帧包含48位控制位和4096位数据位。

假设有两个网桥各连接一对令牌总线局域网(802．4标准)，第一个网桥必须每秒转发1000分组，每个分组为512字节。第二个网桥必须每秒转发200分组，每个分组为4096字节。试问哪个网桥的处理器需要有较高的处理速度?

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

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

因特网的域名空间是一种层次型的_______。()

公开发行股票的运作程序有、、、___。

根据图1．6所示，写出其关联矩阵，指明各个顶点的度，并且指出其偶点与奇点。

设u1，u2u3，u4，u5各点之间的距离表如下：求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。

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

《雷雨》是一出（）

如下_______成立，必使p∧q∧r为假。()

一种与生活愿望相结合并指向于未来的想象是（　　　）。

下列穴位中，可治疗瘾疹、湿疹、丹毒等血热性皮外科病的穴位是

关于两组呈正态分布的数值变量资料，但均数相差悬殊，若比较离散趋势，最好选用下列哪项指标

按现行制度，现金日记账和银行存款日记账必须采用订本式账簿。()

培养德、智、体全面发展的社会主义事业的建设者和接班人的根本途径是()。

在教学中最常用的方法是

在VisualFoxPro中，"表"通常是指

数据结构

理工类

下列选项中不是传输层协议与数据链路层协议相似的地方的是()

信源以字节(8比特)为单位传输数据，若数据速率为B(bit／s)，对下列两种情况分别计算有效数据传输速率：(1)异步串行传输，无校验位、1位停止位；(2)同步串行传输，每帧包含48位控制位和4096位数据位。

假设有两个网桥各连接一对令牌总线局域网(802．4标准)，第一个网桥必须每秒转发1000分组，每个分组为512字节。第二个网桥必须每秒转发200分组，每个分组为4096字节。试问哪个网桥的处理器需要有较高的处理速度?

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

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

因特网的域名空间是一种层次型的_______。()

公开发行股票的运作程序有____________、____________、__________、_____________。

根据图1．6所示，写出其关联矩阵，指明各个顶点的度，并且指出其偶点与奇点。

设u1，u2u3，u4，u5各点之间的距离表如下：求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。

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

《雷雨》是一出（）

如下_______成立，必使p∧q∧r为假。()

一种与生活愿望相结合并指向于未来的想象是（ ）。

下列穴位中，可治疗瘾疹、湿疹、丹毒等血热性皮外科病的穴位是

关于两组呈正态分布的数值变量资料，但均数相差悬殊，若比较离散趋势，最好选用下列哪项指标

按现行制度，现金日记账和银行存款日记账必须采用订本式账簿。()

培养德、智、体全面发展的社会主义事业的建设者和接班人的根本途径是()。

在教学中最常用的方法是

在VisualFoxPro中，"表"通常是指

公开发行股票的运作程序有、、、___。

一种与生活愿望相结合并指向于未来的想象是（　　　）。