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

admin2010-04-24 53

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

数据结构

理工类

在TCP的段结构中，以________表示地址。

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

UDP的段结构中，源端口所占的长度为()

为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为________。

在传输层的两种编址方式为分级结构和________。

下列IP地址中错误的是()

求下面图5．28一图5．30中甲城到乙城的最大通过能力。(1)(2)(3)

某车场每天有5辆车经过4个装卸点A1，A2，A3，A4，巡回运输。在每一个装卸点需要的装卸工人数如图4．7所示。试制定合理调配装卸工人的方案。

有4台机器可同时加工5种零件，费用系数矩阵如表6．11所示，求费用最小的分派方案。

人民检察院对公安机关及其人民警察实施法律监督,主要是通过刑事诉讼活动进行的,其内容和形式主要有()。

一般腰椎牵引时间为

静脉血栓形成可分成两种类型，下述正确的是

A、脓血便B、果酱样便C、米泔水样便D、柏油样便E、白陶土样便阻塞性黄疽大便呈

无牙颌缓冲区需要缓冲的原因是

下列业务属于营业外支出范围的有()。

2010年中国氧化镁产量比2009年增长了()。

通过影响商业银行放款能力来发挥作用的货币政策工具是()。