Question

第八题选什么，为什么

Answer 1

【答案】C

【解析】如图所示，可能的情况有三种，分别有12（情况1）、20（情况2）、21（情况3）个结点，其中最多的有21个（情况3）。

情况1（红色结点表示第四层的叶节点）

情况2（红色结点表示第四层的叶节点）

情况3（红色结点表示第四层的叶节点）

• 完全二叉树的定义：

  如果一个二叉树除最后一层外，其它各层的结点数都达到最大个数（2^(n-1)个），并且最后一层所有的结点都连续地集中在最左边，这样的二叉树就是完全二叉树。

• 完全二叉树的性质：

  （1）所有的叶结点都出现在层次最大的两层；

  （2）完全二叉树中1°的结点数只有0或1个两种可能。

根据完全二叉树的性质（1）可知，该树有4（情况1）或5层（情况2、3）；根据性质（2）又可知，该树第5层有5（情况2）或6（情况3）个结点。由对比易知，情况3结点数最多。

追问

这个图是根据什么画出来的啊

公式吗

追答

根据定义：除最后一层，其它各层都是满的，且最后一层的所有结点都在左边。作图就你需要熟练了，别人用没用公式我不知道，反正我不是根据公式做出来的。

当然，你熟练之后可以不画图（画图浪费时间），直接想出结果：

1. 先判断层数：假设有6层，则第四层不可能有叶节点（因为第5层是满的），所以只可能有4或5层。显然有5层的结点数最多。

2. 再判断个数：有5层时，第四层连了叶节点的结点有3个（8减5），每个最多连2个结点，2×3=6。共1+2+4+8+6=21个。

所以可以总结公式了：

【题】已知完全二叉树T的第n层有m个叶节点，则T的结点个数最多是？

【解】树T有（n+1）层，第n层连了叶节点的结点有[2^(n-1)-m]个，每个最多连2个结点，最后一层有[2^n-2m]个。共1+2+4+……+2^(n-1)+2^n-2m=2^(n+1)-2m-1个。

将题中n=4，m=5代入，得：2^（4+1）-2×5-1=21个。

追问

好吧

感觉太麻烦了

谢谢你啊

追答

不谢。只要把概念理解清楚，动动脑筋，你一定想得明白的！