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

Question

因此，正如标题所暗示的那样，任何人都拥有/知道一种算法（如果可能的话，用java）来生成给定叶子数量的所有可能的二叉树，如下面第二个链接的示例所示？

\n

` N                  N                  N\n / \\                / \\                 /\\\nN   N               N  N               N  N\n/\\   /\\             /\\                     /\\\nN  N  N N           N  N                    N N\n                   / \\                        /\\\n                   N  N                       N N \n

\n

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

\n

Answer 1

我以这种方式解释您的要求：您希望所有由内部节点和叶子组成的二叉树，其中每个内部节点恰好有两个子节点（没有节点只有一个子节点）并且具有给定数量的叶子。

\n

不，我不知道一种算法，但我可以认为设计一个算法太难了。

\n

List<TreeNode> allBinaryTrees(int numberOfLeaves) {\n    if (numberOfLeaves < 1) {\n        throw new IllegalArgumentException("Number of leaves must be positive");\n    }\n    List<TreeNode> result = new ArrayList<>();\n    if (numberOfLeaves == 1) {\n        // return a single tree consisting of a single leaf node\n        result.add(new Leaf());\n        return result;\n    }\n    // We need one node for the root and at least one for the right subtree,\n    // so the size of the left subtree\n    // can only go up to numberOfLeaves - 2.\n    for (int sizeOfLeftSubtree = 1; sizeOfLeftSubtree < numberOfLeaves - 1; sizeOfLeftSubtree++) {\n        List<TreeNode> possibleLeftSubtrees = allBinaryTrees(sizeOfLeftSubtree);\n        List<TreeNode> possibleRightSubtrees = allBinaryTrees(numberOfLeaves - sizeOfLeftSubtree);\n        for (TreeNode lt : possibleLeftSubtrees) {\n            for (TreeNode rt : possibleRightSubtrees) {\n                // make a tree of a node with lt and rt as subtrees,\n                // and add it to the result\n                result.add(new InternalNode(lt, rt));\n            }\n        }\n    }\n    return result;\n}\n

\n

在上面我假设 和InternalNode都是Leaf的子类TreeNode。您可能想要不同的设计。

\n