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

对于一棵二叉树, 设叶子节点数为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 有xa0n0=(n-n1+1)/2

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

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

当n为偶数(即度为1的节点为1个)xa0n0= 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，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。