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

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⌋（向下取整符号不能丢）

扩展资料：

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

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

对于一棵二叉树, 设叶子节点数为n0, 度为1的节点数为n1, 度为2的节点数为n2

度为2的节点有2个分支, 度为1结点有1个分支, 度为0的节点有0个分支

则n0 = n2 + 1(公式1)

证明：

(度为2的节点有2个分支, 度为1结点有1个分支, 度为0的节点有0个分支)

总分支数=2*n2 + n1

另外分支数 = n0 + n1 + n2 - 1 (每个结点上面对应一个分支，除了根节点上面没有分支)

因此 2*n2 + n1 = n0 + n1 + n2 - 1 得 n0 = n2 + 1

假设n为完全二叉树的结点总数, 则有n=n0+n1+n2(公式2)

结合公式 1和2 有 n0=(n-n1+1)/2

又因为 n1 = 0 或者 n1 = 1 只有这两种情况(完全二叉树的性质呀--只有一个分支的节点要么有, 要么没有, 剩下的全是两个分支的节点和0分支的叶子节点)

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

当n为偶数(即度为1的节点为1个) n0= n/2

n1，n2，都可以求。

所以一般做题思路就是，先看总节点个数，是奇还是偶，奇数，可知 n1 = 0。再计算n0,。此时n0， n1都知道了, n2 = n-n1-n0。偶数同上。

扩展资料：

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

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点。

完全二叉树与非完全二叉树一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。