二叉树的排列

Question

考虑二叉树:

1. Ñ是一个节点,如果Ñ是整数
2. (+ a b)是节点,如果a和b是节点.

我们有以下三个操作:

1. (+ a b) - >(+ b a)
2. (+(+ a b)c) - >(+ a(+ b c))
3. (+ a(+ b c)) - >(+(+ a b)c)- (2.反向)

我需要一种算法来使用这些操作给出给定树的所有可能的排列.任何操作都可以应用于任何子树.对于排列,我的意思是任何具有完全相同的叶子集的树.这可能不是很困难,但我似乎无法弄明白.

[编辑]叶子也可以是名称(即变量),因此不能选择依赖于它们的属性作为整数.树确实代表了总和.

[编辑2]这个练习的要点是通过找到形式A和-A的术语来减少总和,调整树以使它们进入子树(+ A -A)以消除它们.上面的三个操作是我系统中的公理,它们需要一直使用,否则无法证明简化树等于原始树.由于我使用的是Twelf逻辑编程语言,如果我能找出算法来做我最初提出的问题,其余的就很容易了,但是替代解决方案当然是受欢迎的.

Answer 1

毫无疑问，这个问题的解决方案将包括加泰罗尼亚数字。有n 个叶子的C _{n -1 种}可能的二叉树，并且有n ! 叶子的可能顺序，所以有n ! * C _{n -1 种}可能的树。不过，枚举它们有点棘手。