2

我需要找到一种算法来生成二叉树的所有可能排列，并且需要在不使用列表的情况下这样做（这是因为树本身带有无法转换为列表的语义和约束）。我找到了一种适用于高度为 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

等等...

4

2 回答 2

3

该结构完全不适合排列，但是由于您知道它是左中心的，因此您可以做出一些假设来帮助您。

我尝试以与您类似的方式工作，但我总是发现您只有一个二进制信息（交换或不交换）是不够的。对于四片叶子，你有四片！(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个。从数学上讲，您根本无法表示排列。

于 2009-03-26T13:42:25.177 回答
0

列出树中所有项目的列表，使用生成方式构建所有可能的顺序（参见 Knuth Vol 4），然后将它们重新映射到树结构有什么问题？

于 2009-03-26T13:34:35.460 回答