我如何生成（并因此找到所有可能的）非同构树，这些树具有二元和三元中间节点，正好给出“L”叶节点

Question

具有以下输入条件

1. 一个根节点，只能有一个输出
2. 有一组固定/有限的恰好“L”个叶节点，比如 20
3. 中间节点可以在二元或三元节点之间选择。中间节点可以是“J2”节点（1 个输入和 2 个输出）和“J3”节点（1 个输入和 3 个输出）的组合

我要求.. 可以构造多少个非同构树，生成所有这些树的算法是什么？

Tree = Tree(Node,Edge) 这样 Node = {root(1), "L" 叶节点, "n" 没有。 “J2”节点和“m”没有。 “J3”节点的数量}，其中 n 和 m 可以采用任何 (+ve) 整数值来满足“L”叶节点。

这个问题出现在管道拓扑优化中。

Answer 1

首先生成节点数最少的树，使用除最后一层连接到叶子的节点之外的所有J3节点，其中需要一些J2节点。

如果 Y 是节点层数，那么您将需要满足 3^Y >= L 的最小层数（最小 Y）。（例如，对于 20 个叶子，最小 Y = 3）

现在用 J2 节点一个接一个地替换 J3 节点，对树进行必要的更改，直到您拥有满足 2^Y >= L 的最小 Y。（例如，对于 20 个叶子，最小 Y = 5）