c - 如何列出具有n个节点的所有可能的二进制搜索树？

我想列出所有可能的二进制搜索树。我知道这个号码将是加泰罗尼亚语号码。但我也想列出他们。

假设我将字母分配给二进制搜索树的每个位置，如下所示



然后要列出具有N个节点的所有可能的树。如果N为1，则唯一可能的树是

A

如果N为2，则可能的树是

A B
A C

如果N为3，则可能的树为

A B D
A B E
A B C
A C F
A C G

如果N为4，则可能的树为

A B D H
A B D I
... should be 12 more

有谁知道列出所有可能的树的好的算法？

最佳答案

一个简单的（天真？）方法包括递归。具有n个节点的二叉树是根，具有k<n节点的二叉树和具有n-1-k个节点的另一个二叉树。

这是与我的方法相对应的Python代码。如果需要，您可以轻松地对输出进行排序。

def binary_trees(n, i=0):
    if not n:
        return [[]]
    else:
        ll=[]
        for k in range(n):
            l1 = binary_trees(k, 2*i+1)
            l2 = binary_trees(n-1-k, 2*i+2)
            for j in l1:
                for l in l2:
                    ll.append([i]+j+l)
        return ll

def numbers_to_letters(l):
    return [chr(i+ord('A')) for i in l]

print [numbers_to_letters(l) for l in binary_trees(4)]

可以通过DP进行改进：计算大小为1，然后2，然后3…的树，并将其保留在内存中以供重用，而不必每次都重新计算。

关于c - 如何列出具有n个节点的所有可能的二进制搜索树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24076440/