一棵完全二叉树上有1001个结点，其中叶子结点的个数是

H爱不绝迹 · 2018-4-30 01:57:37

由完全二叉树性质可知，若给每个结点依次序标上1~n序号，序号为 i 的结点（假设有两个孩纸存在）其左孩纸序号为 2i（皆为偶数），右孩纸序号为 2i + 1 （皆为奇数），故 1001 为右孩子，其父结点序号为 500 （ 2i + 1 = 1001 聽聽解得聽i 聽= 500 ），故n2 = 500 （按规律501的孩纸序号应为501 * 2 = 1002 和 1003，此题一共只有1001个结点，故501 没有孩纸），n1要么为 0 要么为 1 ，奇数个结点时为最后一个叶子结点为右孩纸，偶数个结点时最后一个为左孩纸。
具体如下：
1、简介
完全二叉树的定义、性质以及算法见正文。这里补充一点：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
2、判断完全二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

3、完全二叉树定义
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

_我是名字 · 2018-4-30 01:57:38

n = n。+ n1 + n2
( n: 总结点个数
n。:无孩纸的结点个数（即叶子结点）
n1:有一个孩纸的结点个数
n2:有两个孩纸的结点个数
结点要么有两个孩纸，要么一个，要么没有）
由完全二叉树性质可知，若给每个结点依次序标上1~n序号，序号为 i 的结点（假设有两个孩纸存在）其左孩纸序号为 2i（皆为偶数），右孩纸序号为 2i + 1 （皆为奇数）
故 1001 为右孩子，其父结点序号为 500 （ 2i + 1 = 1001 解得 i = 500 ）
故n2 = 500 （按规律501的孩纸序号应为501 * 2 = 1002 和 1003，此题一共只有1001个结点，故501 没有孩纸）
n1要么为 0 要么为 1 ，奇数个结点时为最后一个叶子结点为右孩纸，偶数个结点时最后一个为左孩纸
此时 n1 = 0 (1001是右孩纸)
n = n。+ n1 + n2
1001 = n。+ 0 + 500
n。= 501

chiconysun · 2018-4-30 01:57:39

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + 1+ n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + 1 + n1 = 1001，n1 =0，因此n2 = 500
所以n0 = 501，即叶子个数是501个

擦人特然 · 2018-4-30 01:57:40

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + n1 = 1000，n1 = 0，因此n2 = 500
所以n0 = 501，即叶子个数是501个

悠悠兮梦 · 2018-4-30 01:57:41

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + n1 = 1001，n1 = 1，因此n2 = 500
所以n0 = 501，即叶子个数是501个

热心网友 · 2018-4-30 01:57:42

上面是错的，，应该是490个

一棵完全二叉树上有1001个结点，其中叶子结点的个数是

6 个回复