algorithm - 不使用列表排列二叉树

Question

我需要找到一种算法来生成二叉树的每种可能的排列，并且需要在不使用列表的情况下这样做(这是因为树本身带有无法转换为列表的语义和限制)。我发现了一种适用于高度为 3 或更少的树的算法，但每当我达到更高的高度时，我就会失去每个添加的高度的一组可能的排列。

每个节点都携带有关其原始状态的信息，以便一个节点可以确定是否已为该节点尝试了所有可能的排列。此外，该节点还携带有关天气的信息，或者是否已“交换”，即是否已看到其子树的所有可能排列。树以左为中心，这意味着右节点应该始终(除了在某些情况下我不需要覆盖该算法)是叶节点，而左节点始终是叶或分支。

我目前使用的算法可以这样描述:

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'

算法的期望行为是这样的:

            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 位。 8 个叶子的排列有 40320 种，而 15 位的可能组合只有 32768 种。从数学上讲，您根本无法表示排列。