求解一个数据结构中树的题目已知完全二叉树的第七层有10个叶子结点,则整个二叉树的结点数最多是多少?由于本题求二叉树的结点数最多是多少,第7层共有27-1=64个结点,已知有10个叶子,其余54

Question

求解一个数据结构中树的题目
已知完全二叉树的第七层有10个叶子结点,则整个二叉树的结点数最多是多少?
由于本题求二叉树的结点数最多是多少,第7层共有27-1=64个结点,已知有10个叶子,其余54个结点均为分支结点.它在第八层上有108个叶子结点.所以该二叉树的结点数最多可达(27-1+108)=235.（注意：本题并未明说完全二叉树的高度,但根据题意,只能有8层.）
请问解答中的它在第八层上有108个叶子结点是怎么算出来的

Answer 1

情况是这样的,由于数据结构中对于完全二叉树的定义各个教材可能不一定相同,那我现在以清华大学出版社的为准来说明：
分析该题,可见该题有2中可能情况,一种是7层,一种是8层,但要求最多,所以一定是8层二叉树.
如果是8层二叉树,7层就一定有2^(7-1)=64个节点,本来这样第八层如果全满的话,就有2^(8-1)=128个节点.但是第七层中却有10个叶子节点,说明前面54个节点是非终端节点,而这54个非终端节点的左右孩子其实就是第八层的终端节点（叶子）,而二叉树中度最大为2,所以要是节点最多,明显第八层叶子叶子也要最多,那最多就有54*2=108,所以最多有127+108=235个节点.
画图作说明：
第7层：1 2 .54 [ 55 56.64]-----第7层的10个叶子
/ \ / \ / \
第8层：1 2 3 4 107 108