节点最少的完全二叉树

节点最少的完全二叉树，也称为最小高度完全二叉树或梅森数(Mason number)对应的完全二叉树，是指每一层都是满的，除了最后一层外，如果不满，则最左边的节点尽可能靠左，这种结构在所有同样节点数的完全二叉树中高度是最小的。

例如，对于9个节点的完全二叉树，它是唯一的，并且高度为3。但对于10个节点，有两棵高度相同的最小完全二叉树，它们的高度也是3，区别在于最后一层的分布。最小高度完全二叉树的存在是通过计算公式确定的，比如第n个梅森数M_n可以由前一个梅森数生成，M_1 = 1, M_n = 8 * M_{(n-1)/2} + 1 对于奇数n，M_n = 4 * M_{(n-1)/2} + 1 对于偶数n。

相关问题

完全二叉树度为1节点

完全二叉树是指除了最后一层外，其它层的节点数都达到了最大值，最后一层的节点都靠左排列。对于完全二叉树，度为1的节点只可能存在于最后一层或者倒数第二层。如果最后一层存在度为1的节点，那么这些节点只有左孩子，没有右孩子。如果倒数第二层存在度为1的节点，那么这些节点只有左孩子，没有右孩子，并且它们的左孩子也只有左孩子，没有右孩子。因此，完全二叉树中度为1的节点个数最多为1个，最少为0个。

已知一棵完全二叉树的第六层有8个叶结点则该完全二叉树的结点个数最多是多少 最少是多少

完全二叉树的第 $k$ 层有 $2^{k-1}$ 个节点，叶子节点只存在于最后几层，因此我们可以得出以下结论：

* 第 $h$ 层到第 $n$ 层共有 $2^{n-h+1}-1$ 个节点。
* 第 $n$ 层最多有 $2^{n-1}$ 个节点。

因为这是一棵完全二叉树，所以第 $6$ 层共有 $2^{6-1}=32$ 个节点，其中有 $8$ 个叶子节点。

最少的情况发生在第 $6$ 层恰好只有 $8$ 个叶子节点，而其他层都是满二叉树的情况，这样总节点数为 $1+2+4+8+16+32=63$。

最多的情况发生在第 $6$ 层有 $8$ 个叶子节点，并且其他层都是满二叉树的情况，这样总节点数为 $1+2+4+8+16+32+64=127$。

因此，该完全二叉树的结点个数最多是 $127$，最少是 $63$。