Question

已知一颗完全二叉树中共有768个结点,则该树中共有 个叶子结点

Answer 1

令二叉树中叶子个数为L, 只有一个孩子的结点数为S， 有两个孩子的结点数为D，所有结点数位n；
则有

1. n=L+S+D
   

2. n-1=2D+S,   原因是除根结点外每个叶子结点都由一条入边， 且该入边是由其父节点引出的；

根据完全二叉树的性质可知S=0或S=1， 从n=768可知 s=1
所以得到方程：
L+D+1=768
2D+1=768-1
解方程有L=384， 即有384个叶子结点。

Answer 2

设二叉树度为0结点个数为n0，度为1的结点个数为n1，度为2结点个数为n2
于是n0 + n1 + n2 = 768
按照二叉树的性质：n0 = n2 + 1，代入得
2n2 + n1 + 1 = 768，显然n1为奇数
考虑到完全二叉树中，最多只有1个度为1的结点 ，因此n1 =1
所以n2 = 383
n0 = 384
应该是理解错了

Answer 3

提供一种解法：
T = n0 + n1 + n2 （按照各度数的结点求和可知）
= 2 * n0 + n1 - 1 （二叉树的n2 = n0 - 1）
768 = 2 * n0 + n1 - 1
由于是完全二叉树，所以n1的取值至少能是0和1，又由于768是偶数所以n1取值为1
n0 = 768 / 2 = 384