algorithm - 如何列出按加泰罗尼亚关系排序的所有二叉树

Question

我正在寻找一种 Lisp 或伪代码中的算法来列出所有按加泰罗尼亚语关系排序的二叉树。

例如我想用输入'(a b c d)得到这个结果：(a (b (c d))) (a ((b c) d)) ((a b) (c d)) ((a (b c)) d) (((a b) c) d)

提前感谢您的帮助。

Answer 1

加泰罗尼亚数字没有定义二叉树的任何特定顺序。最常见的排序是按叶深度的字典顺序降序排列（因此，左重树在平衡树之前排序，平衡树在右重树之前排序）。

要获得此排序，您可以对有叶子的树使用递归算法n，对于所有a+b=n, a>=1, b>=1按 的降序排列的a树，返回由一些有叶子的左孩子a和一些有b叶子的右孩子组成的所有树。也就是说，你在两边递归，并输出笛卡尔积。

一些伪代码：

def gen_trees(a,b):
    left_trees = gen_all_trees(a)
    right_trees = gen_all_trees(b)

    trees = []
    for l in left_trees:
        for r in right_trees:
            trees.append([l,r])
    return trees

def gen_all_trees(items):
    trees = []
    if len(items) == 1:
        trees += [items[0]]
    else:
        for i in range(len(items)-1, 0,-1):
            a = items[:i]
            b = items[i:]
            trees += gen_trees(a,b)
    return trees