考查对二叉树的掌握
问：
?? ?在一棵二叉树上第５层的结点数最多的是？
?? ?a.8
?? ?b.16
?? ?c.32
?? ?d.15
?? ?
解析：
?? ?对于二叉树知识点：
?? ??? ?(1).二叉树第i层的结点数目最多为(i大于等于1)。
?? ??? ?(2).深度为k的二叉树至多有个结点(k大于等于1)。
?? ??? ?(3).在任意一颗二叉树中，若终端节点的个数为n0，度为2的结点数为n2，则n0=n2+1。
?? ??? ?(4).具有n个结点的完全二叉树的深度为log(2)n+1
?? ?
?? ?满二叉树和完全二叉树又是二叉树的两种特殊情形：
?? ??? ?1.满二叉树(FullBinaryTree)
?? ??? ??? ?一颗深度为k且有个结点的二叉树称为满二叉树
?? ??? ??? ?特点如下：
?? ??? ??? ??? ?每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
?? ??? ??? ??? ?满二叉树中不存在度数为1的节点，每个分支结点均有两颗高度相同的子树，且树叶都在最下一层。
?? ??? ?
?? ??? ?2.完全二叉树
?? ??? ??? ?若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
?? ??? ??? ?特点如下：
?? ??? ??? ??? ?满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
?? ??? ??? ??? ?在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是完全二叉树
?? ??? ??? ??? ?在完全二叉树中，若某个节点没有左孩子，则它一定没有右孩子，及该节点必是叶结点。在图7的c中，结点F没有左孩子而有右孩子L，故它不是一颗完全二叉树。图7的b是完全二叉树。
?? ?
?? ?
答：
?? ?b
?
?