考虑一个二叉树:
我们执行以下三个操作:
我需要一种使用这些操作来给出给定树的所有可能排列的算法。任何操作都可以应用于任何子树。对于排列，我的意思是任何具有完全相同的叶子集的树。这可能不是很困难，但是我似乎无法弄清楚。
[编辑]叶子也可以是名称(即变量)，因此不能将其属性视为整数。树木确实代表总和。
[Edit2]此练习的目的是通过查找形式为A和-A的项来减少总和，将这些树摇动以使其成为子树(+ A -A)以消除它们。上面的三个操作是我系统中的公理，必须一直使用它们，否则无法证明简化后的树等于原始树。由于我使用的是Twelf逻辑编程语言，因此，如果我能找到一种算法来完成我最初要求的工作，那么其余的工作就很容易进行了，但是当然也欢迎使用其他解决方案。
最佳答案
似乎最直接的解决方案是对树进行深度优先遍历，以将所有节点收集到列表中，生成列表的所有排列，并将每个排列转储到二叉树中。
因此，给定列表(+ 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元组是一组节点。对于多个节点，在您的算法完成之前，Universe将经历热死。