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

Answer 2

搜