给定L个叶节点的非异构混合二叉/三叉中间节点树的计数与生成算法咨询

一、核心约束推导 #

首先根据节点端口平衡（输出端口总数=输入端口总数），推导中间节点数量的约束：
设叶节点数为$L$，二叉中间节点数为$n$，三叉中间节点数为$m$，则必须满足：
n + 2m = L - 1
以示例$L=20$为例，$n=19-2m$，$m$可取0_{9（若允许单独使用某类中间节点）；若要求$n,m$为正整数，则$m$可取1}9，对应$n$为17、15…1。

二、非异构树计数 #

非异构树的定义为拓扑结构不同的树，需区分两种场景：有序树（分支顺序不同算不同结构，如管道分支有左右区分）和无序树（分支顺序不影响，如管道分支无方向差异）。

1. 有序树（平面树）计数 #

采用动态规划递推，定义$a_k$为含$k$个叶节点的有序树总数：

• 边界条件：$a_1 = 1$（仅根节点直接连1个叶节点）
• 递推公式：
  $$
  a_k = \sum_{i=1}^{k-1}a_i a_{k-i} + \sum_{\substack{i+j+l=k \ i,j,l \geq1}}a_i a_j a_l
  $$
  其中：
  • 第一项对应二叉中间节点的所有分支组合（有序，$i$和$k-i$顺序不同算不同结构）
  • 第二项对应三叉中间节点的所有分支组合（有序，$i,j,l$顺序不同算不同结构）

以$L=20$为例，通过递推计算可得$a_{20}$即为有序树总数。

2. 无序树（非平面树）计数 #

需考虑分支的无序性，递推时去重：

• 边界条件：$a_1 =1$
• 递推公式：
  $$
  a_k = \frac{1}{2}\left(\sum_{i=1}^{k-1}a_i a_{k-i} - \sum_{i=1}^{\lfloor(k-1)/2\rfloor}a_i a_{k-i} \cdot [i \neq k-i]\right) + \frac{1}{6}\left(S - 3S_2 - 2S_3\right)
  $$
  其中：
  • $S = \sum_{\substack{i+j+l=k \ i,j,l \geq1}}a_i a_j a_l$
  • $S_2$为两分支相同、一分支不同的组合数总和
  • $S_3$为三分支全相同的组合数总和
  • 系数用于消除有序组合的重复计数（如二叉分支$i+j$与$j+i$算同一种）

三、生成所有树的算法 #

1. 有序树生成（递归回溯） #

1. 节点结构定义：包含节点类型（root/leaf/J2/J3）、有序子节点列表。
2. 递归函数逻辑：
   • 输入：目标叶节点数$k$
   • 输出：所有含$k$个叶节点的有序树列表
   • 步骤：
     • 若$k=1$：返回仅根节点连1个叶节点的树。
     • 若$k\geq2$：
       • 生成二叉分支：遍历$i=1$到$k-1$，递归生成$i$叶节点树$T_1$和$k-i$叶节点树$T_2$，创建J2节点并将$T_1$、$T_2$作为子节点，root连接该J2节点，加入结果。
       • 生成三叉分支：遍历所有$i,j,l\geq1$且$i+j+l=k$，递归生成$T_1(i)$、$T_2(j)$、$T_3(l)$，创建J3节点并将三者作为子节点，root连接该J3节点，加入结果。

2. 无序树生成（递归回溯+去重） #

1. 节点结构定义：包含节点类型、无序子节点集合（或排序后的列表用于去重）。
2. 递归函数逻辑：
   • 输入：目标叶节点数$k$
   • 输出：所有含$k$个叶节点的无序树列表
   • 步骤：
     • 若$k=1$：返回单叶节点树。
     • 若$k\geq2$：
       • 生成二叉分支：遍历$i=1$到$\lfloor k/2\rfloor$，$j=k-i$：
         • 若$i<j$：递归生成$T_1(i)$和$T_2(j)$，组合所有$T_1$与$T_2$，创建J2节点加入结果。
         • 若$i=j$：递归生成$T(i)$，取$T$的两两组合（含自身），创建J2节点，避免重复（如通过树结构哈希判断）。
       • 生成三叉分支：遍历$i\leq j\leq l$且$i+j+l=k$：
         • 按$i,j,l$的相等情况（全不同/两同/全同），递归生成对应子树，组合后创建J3节点，加入结果时通过结构哈希去重。

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