第 8 题

根结点所在层为第1层。高度为k的完全二叉树，前k－1层均已填满，因此左右子树在这些层中的结点个数相同，差值n只由第k层决定。

第k层共有2^(k－1)个位置，分属左右子树的各有2^(k－2)个。令h＝2^(k－2)，最后一层按从左到右的顺序填入结点：

• 只填到左半部分时，右半部分为空，n随左半部分结点数增加，最大为h。
• 左半部分填满后，再向右半部分填入结点，n从h逐渐减小；整层填满时n＝0。

所以0≤n≤2^(k－2)。左半部分恰好填满、右半部分为空时可取2^(k－2)；再向右半部分填入1个结点时可取2^(k－2)－1；整层填满时可取0。2^(k－2)＋1超过最大差值，不可能出现。