8. 已知完全二叉树的第 7 层有 20 个叶结点，则该二叉树最多有（ ）个结点。 A.83 B.147 C.214 D.215

对于一棵深度为 $k$ 的完全二叉树，其叶结点的数量为 $2^{k-1}$。已知第 7 层有 20 个叶结点，则该完全二叉树最多有 $2^6-1+20\times2=147$ 个结点，选项 $\mathbf{B}$ 正确。其中 $2^6-1$ 表示前 6 层的结点数量，$20\times2$ 表示第 7 层的结点数量。

相关问题

写出下面的答案3.已知完全二叉树的第6层有10个结点，则该完成二叉树共有 个结点。 4.已知一颗完全二叉树，结点编号从0开始按层次遍历，结点i （i>0）的双亲结点编号是 。 5.已知一颗完全二叉树，结点编号从1开始按层次遍历，结点i 的右孩子结点编号是 ,左孩子结点编号是 。 6.已知Huffman树有n个叶子结点，则它的结点总数为 。 7.如果二叉树的深度为5，则其结点数目最少为 , 最多为 。 8.如果一颗二叉树的先序遍历和中序遍历顺序相同，则该二叉树 ；如果其先序遍历和后序遍历顺序相同， 则该二叉树 。

3. 该完全二叉树共有 2^6 - 1 + 10 = 75 个节点。
4. 结点 i 的双亲结点编号为 (i-1)/2。
5. 结点 i 的右孩子结点编号为 2i，左孩子结点编号为 2i+1。
6. Huffman 树共有 2n-1 个结点。
7. 结点数目最少为 2^5 - 1 = 31，最多为 2^6 - 1 = 63。
8. 如果一颗二叉树的先序遍历和中序遍历顺序相同，则该二叉树是一颗斜树；如果其先序遍历和后序遍历顺序相同，则该二叉树为一颗满二叉树。

已知一棵完全二叉树的第六层有8个叶结点则该完全二叉树的结点个数最多是多少 最少是多少

完全二叉树的第 $k$ 层有 $2^{k-1}$ 个节点，叶子节点只存在于最后几层，因此我们可以得出以下结论：

* 第 $h$ 层到第 $n$ 层共有 $2^{n-h+1}-1$ 个节点。
* 第 $n$ 层最多有 $2^{n-1}$ 个节点。

因为这是一棵完全二叉树，所以第 $6$ 层共有 $2^{6-1}=32$ 个节点，其中有 $8$ 个叶子节点。

最少的情况发生在第 $6$ 层恰好只有 $8$ 个叶子节点，而其他层都是满二叉树的情况，这样总节点数为 $1+2+4+8+16+32=63$。

最多的情况发生在第 $6$ 层有 $8$ 个叶子节点，并且其他层都是满二叉树的情况，这样总节点数为 $1+2+4+8+16+32+64=127$。

因此，该完全二叉树的结点个数最多是 $127$，最少是 $63$。