Question

若完全二叉树的第6层有10个叶结点，则该完全二叉树结点总数最多是。 A．107 B．108 C．234 D．235

求详细具体的算法，为什么要这样算？

Answer 1

选A
解析：由题意得：这棵二叉树最多有7层
在第6层满的情况下，有2^(6-1)=32，其中非叶子节点有32-10=22，而非叶子节点最多有两个孩子从而第七层上共有22*2=44个节点。
又前6层的节点数为：2^6-1=63
所以这棵二叉树的节点数最多为63+44=107个

Answer 2

求最多，肯定前六层是满的，然后共有63个节点根据性质2求的。
然后，重点是求第七层，最大共有32-10=22，22*2=44个节点。
63+44=107个节点。

Answer 3

题目：若完全二叉树的第6层有10个叶结点，则该完全二叉树结点总数最多是及最少是？
根据完全二叉树的性质，叶子结点只可能在层次最大的两层上出现，故分以下两种情况：
①二叉树节点总数最多，即最大层树为7，则根据完全二叉树的性质可知，前6层为满二叉树，而第七层缺失了10*2=20各结点，故完全二叉树的结点个数最多为2^7-1-(10*2)=107
②二叉树节点总数最少，即最大层数为6，则根据完全二叉树的性质可知，前5层为满二叉树，
前五层的结点总数为：2^5-1=31，再加上第六层的10个叶子结点，故完全二叉树结点个数最少为：2^5-1+10=41

Answer 4

A

追问

为什么选A？怎样算的？