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

Question

我想列出所有可能的二叉搜索树。我知道该号码将是加泰罗尼亚语号码。但我也想列出它们。

假设我为二叉搜索树的每个位置分配字母，如下所示

然后想要列出所有可能的具有 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

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

Answer 1

一个简单的（天真的？）方法包括递归。具有 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 的树……并将它们保存在内存中以供重用，而不是每次都重新计算。