置换二叉树，而无需使用列表

Question

我需要找到用于产生二进制树的每一种可能的置换的算法，并且需要在不使用列表来这样做（这是因为树本身携带的语义和限制不能被翻译成列表）。我发现，三个或更少的高度，树木作品的算法，但每当我得到更高的境界，我失去添加一组每高度的可能的排列。

每个节点携带关于其原始状态信息，使得一个节点能够确定是否所有可能的排列已被尝试针对该节点。此外，节点进行气象信息它是不是被“交换”，即如果它已经看到了所有可能的排列它的子树。树是左为中心，这意味着正确的节点应该始终（除了在某些情况下，我并不需要覆盖这个算法）是叶节点，而左侧节点始终为叶或分支。

我使用的时刻该算法可排序的描述是这样的：

if the left child node has been swapped
      swap my right node with the left child nodes right node
      set the left child node as 'unswapped'
  if the current node is back to its original state
      swap my right node with the lowest left nodes' right node
      swap the lowest left nodes two childnodes
      set my left node as 'unswapped'
      set my left chilnode to use this as it's original state
      set this node as swapped
      return null
  return this; 
else if the left child has not been swapped
  if the result of trying to permute left child is null
     return the permutation of this node
  else 
     return the permutation of the left child node
if this node has a left node and a right node that are both leaves
   swap them
   set this node to be 'swapped'

的

algoritm的期望的行为将是这样的：

            branch
             /    |
       branch     3
         /   |
   branch    2
   /     |
  0      1


            branch
             /    |
       branch     3
         /   |
   branch    2        
   /     |
  1      0           <-- first swap



            branch
             /    |
       branch     3
         /   |
   branch    1         <-- second swap
   /     |
  2      0



            branch
             /    |
       branch     3
         /   |
   branch    1         
   /     |
  0      2   <-- third swap


            branch
             /    |
       branch     3
         /   |
   branch    0   <-- fourth swap        
   /     |
  1      2  

和等等...

Answer 1

在结构仅仅是排列完全不适应，但既然你知道它的左心你也许可以作出一些假设，帮助你。

我试图与你相似的方式工作，而我总是被抓住了这样的事实，你只有一个二进制一块这是不足够的信息（换与否）。对于四片叶子，你有4个！ （24）可能的组合，但你只有真正有三个分支（3位，8个可能的组合）来存储交换状态信息。你根本就没有存储这些信息的地方。

但是，也许你可以写一个横移，通过树去，并用叶子的数量来确定多少互换需要，然后通过这些掉期进入系统，而不是仅仅把它留给树本身。

像

的东西

For each permutation
   Encode the permutation as a series of swaps from the original
   Run these swaps on the original tree
   Do whatever processing is needed on the swapped tree

这可能不适合你的应用程序，但是你有没有考虑到，为什么你需要做它，你正在做的方式很多细节。你正在做的，现在根本不会工作的方式，因为阶乘（排列的数量）增长高于指数（你有“交换”的个数）更快。如果你有8个叶子，你将有7个分公司和8个叶，总共15位。有40320排列8个叶子，只有32768的15位可能的组合。在数学上，只需不能代表排列。

Answer 2

什么是错使树中的所有项目的列表，使用生成的手段来构建所有可能的顺序（见克努特第4卷），然后将它们重新映射到树形结构？