Question

计算机二级关于二叉树的问题。懂的进，急求解答。

1.在深度为5的满二叉树中，叶子结点的个数为（）
A.32 B.31 C.16 D.15
答案是B还是C？
2.设一棵完全二叉树共有500个结点，则在该二叉树中有（250）个叶子结点。
3. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为350。
4.设一棵完全二叉树共有700个结点,则在该二叉树中有( 350)个叶子结点
求高人解答为什么第3.4题的总结点数不一样，而叶子结点一样呢？
遵循原则：在二叉树中，度为0的结点总比度为2的结点多1个。
我错在哪里了？

Answer 1

1.如果有一颗深度为h的满二叉树，
　　它的叶子数是： 2^(h-1) 选c

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
　　可以根据公式进行推导，假设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，就可根据完全二叉树的结点总数计算出叶子结点数。 所以叶子结点数相同

追问

能不能就第3.4两题进行一下具体讲解呀？我还是有点不明白为什么总结点数一个为699，一个为700，而叶子结点相同。谢啦！(*^__^*) 嘻嘻……

追答

n0=（n+1）/2或n0=n/2， 这个公式啊~的出来的啊