Question

完全二叉树叶子节点的算法?

求讲解...不要百科上的.就是公式:n0＝（n＋1）/2怎么推导的- -谢谢了

Answer 1

设二叉树的叶子节点数为n0，度数为2的节点数为n2，设n1为二叉树中度为1的节点数

因为二叉树中所有节点的度都钓鱼或者等于2，所以二叉树节点总数n=n0+n1+n2

再看二叉树的分支数，除了根节点外，其余节点都有一个分支进入，设B为分支总数，则n=B+1

由于这些分支都是有度为1或者2 的节点射出的，所以B=n1+n2;于是有n=n1+2*n2+1

综合n=n0+n1+n2和n=n1+2*n2+1两式即可得到n0=n2+1

完全二叉树是特殊的二叉树，对于n0=n2+1当然成立

Answer 2

设二叉树中度为0叶子有n0个，度为1 结点有n1 个，度为2 结点有n2个
n0 + n1 + n2 = n (1)
按照二叉树性质：n0 = n2 + 1，也就是n2 = n0 -1
于是代入(1) 得：2n0 + n1 - 1 = n
按照完全二叉树性质，度为1 的结点最多1个
因此当n为偶数时，n1 = 1，因此n0 = n / 2
当n为奇数时，n1 = 0，因此n0 = (n + 1)/2
合并这两个结果有：n0 = (n + 1)/2 ，实际是整数除法，也就是下取整