考查对二叉树的掌握
问:
在一棵二叉树上第5层的结点数最多的是?
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