完全二叉树的叶子节点数公式是什么？

~

完全二叉树的叶子节点数公式为：

设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。

1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。

2、当n为偶数（即度为1的节点为1个）， n0= n/2。

n1，n2，都可以求。

特殊类型：

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

相关术语：

1、结点：包含一个数据元素及若干指向子树分支的信息。

2、结点的度：一个结点拥有子树的数目称为结点的度。

3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

以上内容参考   百度百科-二叉树

n0＝（n＋1）/2

设：度为i的结点数为ni，由二叉树的性质可知：

n0 = n2 + 1……………………①式

n = n0 + n1 + n2……………②式

由①式可得 n2 = n0 - 1，带入②式得：

n0 = （n + 1 - n1）/ 2

由完全二叉树性质可知：

如图，当n为偶数时，n1 = 1， n0 = n / 2

如图，当n为奇数时，n1 = 0，n0 = （n + 1）/2

将两式合并，写作：n0 = ⌊（n+1）/2⌋（向下取整符号不能丢）

二叉树的存储结构

按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。

但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。

完全二叉树的叶子节点数公式是：
L = n2
其中，L表示叶子节点数，n表示完全二叉树的节点总数（包括叶子节点和非叶子节点）。
这个公式的推导过程如下：
1. 对于一棵深度为h的完全二叉树，最后一层节点的个数为2^h-1，因为完全二叉树的特性是最后一层节点总是填满的。
2. 除去最后一层节点，剩下的节点数为n-1，这些节点构成了深度为h-1的子树。
3. 因为深度为h-1的子树也是完全二叉树，所以根据上面的推导过程，它的最后一层节点的个数也为2^(h-1)-1。
4. 整个深度为h的完全二叉树的节点数可以表示为：
n = 2^h-1 + n-1
5. 当h>1时，化简上式得到：
n = (2^h-1) + 1
= 2^h
6. 因为最后一层节点都是叶子节点，所以叶子节点数为2^h-1，即L = n2。
需要注意的是，这个公式只适用于完全二叉树，对于其他类型的二叉树（比如满二叉树、平衡二叉树、普通二叉树等）并不适用。

---

温岭市13212982089： 完全二叉树叶子节点个数计算问题 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为______. - ？
闽莫二乙：[选项] A. 349 B. 350 C. 255 D. 351 计算公式是什么样的?

温岭市13212982089： 告诉了一棵完全二叉树的总结点个数,求叶子结点个数怎么计算?谢谢帮助 - ？
闽莫二乙： 前九层的结点就有2^9-1=511个 而第九层的结点数是2^(9-1)=256 所以,第十层的叶子结点数是699-511=188个现在来算第九层的叶子结点个数:由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点.因为第十层...

温岭市13212982089： 二叉树的叶子节点数如何计算? - ？
闽莫二乙： 二叉树的叶子节点数:没有子树的结点是叶子结点.结点的度是指,该结点的子树的个数,在二叉树中,不存在度大于2的结点. 计算公式:n0=n2+1 n0 是叶子节点的个数 n2 是度为2的结点的个数 n0=n2+1=5+1=6 故二叉树有5个度为2的结点,则该二叉树中的叶子结点数为6.

温岭市13212982089： 计算一棵树有56789个节点的完全二叉树中叶子节点的个数 - ？
闽莫二乙：[答案] 深度为15的满二叉树有2^15-1=32767个结点. 所以第16层的叶子结点数量:56789-32767=24022个 第15层的叶子结点数量:2^14-24022/2=16384-12011=4373 叶子结点的总数量:24022+4373=28395个

温岭市13212982089： 数据结构 一棵完全二叉树,第8层含有5个结点,则这棵二叉树的叶子结点个数为? - ？
闽莫二乙：[答案] 这棵二叉树的结点个数为 2^7 - 1 + 5 = 132 二叉树的叶子结点数等于(总结点数 + 1) / 2(向下取整),因此叶子结点数等于133 / 2 = 61

温岭市13212982089： 二叉树的叶子结点数怎么算? - ？
闽莫二乙： 深度为N,节点数为(2^N)-1,叶子节点为2^(N-1),2^N表示2的N次方.

温岭市13212982089： 如果知道完全二叉树上有1001个结点,其叶子结点的个数为多少? - ？
闽莫二乙：[答案] 深度为9的节点数是511,深度为10的节点数是1023,该树为10层, 最后一层节点是1001-511=490(均是叶子节点),最后一层490个节点对应的第9层得父节点有245个,第9层节点共有256个节点,所以第9层叶子节点有256-245=11个 总的叶子节...

温岭市13212982089： 告诉了一棵完全二叉树的总结点个数,求叶子结点个数怎么计算?设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点个数为?怎么计算, - ？
闽莫二乙：[答案] 首先需要求出这棵树的深度.也就是说这棵树有多少层. 完全二叉树有一个性质: 具有n个结点的完全二叉树的深度为log2n(2是下标)+1. 根据这个性质,就可以求得完全二叉树的深度为10 10层满二叉树的总结点数为1023,最后一层的结点数应该是2的...

温岭市13212982089： 一颗完全二叉树上有1001个结点,其中叶子结点的个数 - ？
闽莫二乙：[答案] 1023是满二叉树,有512片叶子.1001比1023少22个结点,所以有512-22+22/2=501片叶子. 511是满二叉树,有256片叶子.1001比511多490个结点,所以有256+490-(490+1)/2=501片叶子. 所以答案就是501了.

温岭市13212982089： 一个完全二叉树上有101个结点,其中叶子结点的个数应该是多少,为什么?用下面公式,公式:2的(k - 1)次方 - 1101我已推出K=7,后面的就不会了.应该是... - ？
闽莫二乙：[答案] K = 7层,完全二叉树就是满二叉去掉或者不去掉右边底层的一些东西.所以你能确定的就是这棵树高度7并且前6层是满二叉树.前6层结点个数应该是2的(K)次方-1 即63个结点.剩余结点个数为 38个结点.也就是说这38个结点处在第七层.当前这叶子结...