求高度为h的完全满二叉树的满子树集合的数量与枚举（初等解法）

嘿，这个问题我刚好能用初等的分层求和思路拆解清楚，咱们先把概念对齐，再一步步算数量，最后说怎么枚举：

避免歧义，先明确几个关键术语：

• 高度为h的完全满二叉树：根在第0层，叶子在第h层，每一层刚好有$2^d$个节点（d是层数），每个非叶节点都有左右两个子节点，是最标准的那种满二叉树。
• 满子树：原树里的一个子结构，本身得是满二叉树——要么是单个节点（没有非叶节点，自然满足条件），要是有多个节点，那每个非叶节点都得在子树里有两个子节点。

咱们用分层统计的思路来算，很直观：

1. 先看原树的每一层：深度为d的节点一共有$2^d$个（从d=0的根节点，到d=h的叶子节点）。
2. 对每个深度d的节点u，它能当多少个满子树的根？
   • 满子树的高度k可以从0取到h-d：
     • k=0：就是u自己一个节点，这是合法的满子树
     • k=1：u加上它的左右两个子节点（原树是满的，这俩肯定存在）
     • ...
     • k=h-d：u加上它所有h-d层的后代，刚好到原树的叶子，构成高度h-d的满二叉树
   • 所以每个深度d的节点对应$(h-d+1)$个满子树。
3. 总数量就是把所有层的数量加起来：
   $$
   |\mathcal S_h| = \sum_{d=0}^h 2^d \cdot (h - d + 1)
   $$
4. 咱们用初等代数把这个求和式化简成闭合式（用错位相减法或者现成的求和公式都行），最终得到：
   $$
   |\mathcal S_h| = 2^{h+2} - h - 3
   $$
   举几个小例子验证下：
   • h=0（只有一个叶子）：$2^2 -0-3=1$，完全正确
   • h=1（根+两个叶子）：$2^3 -1-3=4$，对应4个满子树：根节点、左叶子、右叶子、整棵树
   • h=2：$2^4 -2-3=11$，手动数的话也刚好是11个，没错

有两种很直观的枚举方法，看你习惯哪种：

方法1：按根节点的深度来枚举 #

• 从原树的第0层（根）到第h层（叶子），一层一层遍历：
  • 对每层的每个节点u：
    • 依次生成高度从0到h-d的满子树：
      • 高度0：就只取u这一个节点
      • 高度≥1：取u加上它往下k层的所有后代节点（原树是满的，这些节点都存在，凑起来就是合法的满子树）

方法2：按满子树的高度来枚举 #

• 从高度0到高度h，遍历每个可能的满子树高度k：
  • 所有高度为k的满子树，它们的根节点必须是原树中深度≤h-k的节点（不然根节点往下凑不出k层后代）
  • 每个符合条件的根节点，对应唯一的高度k的满子树：就是根节点加上它往下k层的所有后代

内容的提问来源于stack exchange，提问作者sitiposit