algorithm - 二叉树的排列

Question

考虑一个二叉树:

1. n是一个节点，如果n是一个整数
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. in reverse)

我需要一种算法来使用这些操作给出给定树的所有可能排列。任何操作都可以应用于任何子树。对于排列，我指的是具有完全相同的一组叶子的任何树。这可能不是很困难，但我就是想不通。

[编辑] 叶子也可以是名称(即变量)，因此不能将它们的属性作为整数来依赖。树确实代表总和。

[Edit2] 本练习的要点是通过查找形式为 A 和 -A 的项来减少总和，调配树以将它们放入子树(+ A -A) 来消除它们。以上三个操作在我的系统中是公理，必须一路使用，否则无法证明缩减后的树与原树相等。因为我正在使用 Twelf逻辑编程语言，如果我能想出一个算法来完成我最初提出的要求，剩下的就很容易了，但当然欢迎其他解决方案。

Answer 1

似乎最直接的解决方案是对树进行深度优先遍历，将所有节点收集到列表中，生成列表的所有排列，将每个排列转储到二叉树中。

因此，给定列表 (+ a (+ b c) )，我们有节点 [a; b; c]，具有以下排列:

[a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

列表中的第一项是你的头，接下来的两项是子节点，接下来的四项是子节点，依此类推。

这个 increases dramatically 的复杂性如果您需要生成所有可能树的列表，而不仅仅是平衡树。在这种情况下，您需要像这样对它们进行分组:

[a; b; c; d]
[(a; b); c; d]
[(a; b; c); d]
[a; (b; c); d]
[a; (b; c; d)]
[a; b; (c; d)]
[a; b; d; c]
// first permutation
[(a; b); d; c]
[(a; b; d); c]
...

其中每个 n 元组是一组节点。对于多个节点，在您的算法完成之前，宇宙将经历热寂。