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 个可能的组合。从数学上讲，您根本无法表示排列。