相关疑难解决方法(0)

我无法想出我需要它的情况.

目前,我可以使用以下暴力Prolog代码枚举带根的 平面 未标记二进制树.

e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].

注意:请参阅下面的输出列表.

并使用增加大小输出它们

es(S) :-
    length(Ls, _),
    phrase(e, Ls),     % or e(Ls,[]),
    atomic_list_concat(Ls,S).

然而,这是低效的强力算法.

是否有更有效的算法来枚举带根的平面未标记二进制树？

注意:树可以通过使用前两次迭代中的树来生成,想一想Fibonacci数,并添加一元分支或二元分支,但这会导致重复的树.我自己可以做那个版本,我正在寻找的是一种算法,它可以在没有重复的情况下以高效的方式生成树.

注意:二叉树也称为二进制表达式树或K <= 2 的K-ary树.

补充

结果

我对M(15)的暴力版本需要1小时27分钟,而M(15)的高效版本需要大约2秒钟.

显然,有效的算法就是这样,效率更高,为什么我问这个问题.

莫兹金数字

具有N根节点平面未标记二进制树的节点的树的数量由Motzkin数给出.见:OEIS A001006

Nodes  Trees
1      1
2      1
3      2
4      4
5      9

具有N个内部节点的树的数量由带有根的平面未标记二进制树由加泰罗尼亚数字给出.有一种更有效的算法,用于使用加泰罗尼亚数生成有根平面二叉树.

注意:
基于加泰罗尼亚数字的树的数量没有一元分支,只计算内部节点.

而

基于Motzkin数字的树的数量 …