给定 n 个叶子生成所有可能的二叉树

Question

因此，正如标题所暗示的那样，任何人都知道/知道一种算法（如果可能，在 java 中）生成所有可能的二叉树，如第二个示例中的叶子数 link下面？

` N                  N                  N
 / \                / \                 /\
N   N               N  N               N  N
/\   /\             /\                     /\
N  N  N N           N  N                    N N
                   / \                        /\
                   N  N                       N N

我已经去过 this , this, this and this，但我已经尝试实施每一个，但他们没有做我正在寻找的事情或没有正确解释。如果我必须首先生成所有可能的字符串，然后将它们解析为树类型（parent-children 关系），那么第一个将需要大量计算，而第二个不打印所有树。因为，例如，如果我像上面的例子一样通过指定 3 个内部节点来执行，它只会打印一棵树（左边的那棵）。我从对加泰罗尼亚数字的研究中了解到，即使对于少量节点，树的数量也会增加很多，但是对于少量节点来说是一个有用的工具。

Answer 1

不，我不知道算法，但我认为设计一个算法不会太难：

List<TreeNode> allBinaryTrees(int numberOfLeaves) {
    if (numberOfLeaves < 1) {
        throw new IllegalArgumentException("Number of leaves must be positive");
    }
    List<TreeNode> result = new ArrayList<>();
    if (numberOfLeaves == 1) {
        // return a single tree consisting of a single leaf node
        result.add(new Leaf());
        return result;
    }
    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves; sizeOfLeftSubtree++) {
        List<TreeNode> possibleLeftSubtrees = allBinaryTrees(sizeOfLeftSubtree);
        List<TreeNode> possibleRightSubtrees = allBinaryTrees(numberOfLeaves - sizeOfLeftSubtree);
        for (TreeNode lt : possibleLeftSubtrees) {
            for (TreeNode rt : possibleRightSubtrees) {
                // make a tree of a node with lt and rt as subtrees,
                // and add it to the result
                result.add(new InternalNode(lt, rt));
            }
        }
    }
    return result;
}

在上面我假设 InternalNode 和 Leaf 都是 TreeNode 的子类。

给定 n 个叶子生成所有可能的二叉树

Generating all possible binary trees given n leaves

java

algorithm

tree

binary-tree

permutation