Question

已知完全二叉树的N个结点，该二叉树有多少个叶子结点？

已知完全二叉树的N个结点，该二叉树有多少个叶子结点？
如题！

Answer 1

(N + 1) / 2
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2 ，就可根据完全二叉树的结点总数计算出叶子结点数。

Answer 2

设完全二叉数有N个结点
从根结点开始按每一层从左到右的顺序,用自然数:1,2,3,... ...,N给结点进行编号.
设编号为K,即K=1,2,3,... ...,N
然后有以下3种情况:
1、K=1该结点为根结点,它没有父结点.
K>1,该结点父结点编号为int(K/2).
2、2K<=N,左结点为2K.
3、2K+1<=N,右结点为2K+1.

Answer 3

（n＋1）/2
或N/2

综合起来就是（n＋1）/2，结果只取整数。

Answer 4

有N+1个