BST的输入可能的排列 [英] Possible permutations of BST's input

问题描述

我给出一个字符串，即CPHBDZ。通过将（按顺序）的信件到BST我将有：

I am given a string, i.e. "CPHBDZ". By inserting (in this order) letters to a BST I will have:

  C
 / \
B   P
   / \
  H   Z
 /
D

如果我们改变秩序的字符串为CBPHDZ我们会得到相同的树。 我必须找到并列出提供相同的BST输入字符串的所有排列。我想出了如何计算一个数字的排列组合，但我想不出任何算法实际上找到它们。

If we change order of the string to "CBPHDZ" we will get identical tree. And I have to find and list all permutations of the input string that provide the same BST. I came up with how to calculate a number of those permutations but I can't figure out any algorithm which actually finds them.

推荐答案

假设你没有做任何旋转（等）来平衡树，可以从树的结构得到一个答案：新节点总是添加为现有节点的后裔，所以任何节点树高必须$自有后人p $ pcede，但可以随意重新安排它的同伴（任何既不其父也不后代）。

Assuming you're not doing any rotations (etc.) to balance the tree, you can derive an answer from the structure of the tree: new nodes are always added as descendants of existing nodes, so any node higher in the tree must precede of its own descendants, but can be rearranged at will with its "peers" (anything that's neither its parent nor descendant).

例如，既然你有 C 作为树的根， C 一定是第一个项目这是从流中读取。由于它的后代是 B 和 P ，输入的下一个项目必须是这两个中的一个。 B 没有任何后裔，但 P 有两个： ^ h 和以Z ，所以他们不得不 P 之后读取，但可以在任何顺序相对于 B 。同样，以Z 可以是对于任何以 ^ h 和 D ，而 ^ h 必须precede D 。

For example, since you have C as the root of the tree, C must have been the first item that was read from the stream. Since its descendants are B and P, the next item in the input had to be one of those two. B doesn't have any descendants, but P has two: H and Z, so they had to be read after P, but can be in any order with respect to B. Likewise, Z can be in any order with respect to H and D, but H must precede D.

编辑：至于生成所有排列，一个简单的（作弊）的方法是使用的Prolog。基本上，你恩code，它依赖的事实，它会生成所有适合这些事实的排列。事实上（没有双关语意），这是pretty的什么Prolog是太大的说明/一样。

As to generating all those permutations, one simple (cheating) way would be to use Prolog. Basically, you encode that dependencies as "facts", and it'll generate all the permutations that fit those facts. In fact (no pun intended), this is pretty much a description of what Prolog is/does.

在你自己做，你可能想要做的大部分工作的递归。一个有效的排序是根其次是它的后代有效订单中的任何交织。

Doing it on your own, you'd probably want to do most of the job recursively. A valid ordering is a root followed by any interleaving of the valid orders of its descendants.

至于怎么做交织，你会（例如）产生的左子树的一个有效秩序和右子树的一个有效订单。把它们放在一起与来自左子树中的所有项目在一开始，所有来自右子树在最后的数组。为了演示，让我们假设树中还包含一个 A （如 B 您展示的后代）。在一个阵列，从我们的子树我们的数据看起来像：

As far as how to do the interleaving, you would (for example) generate one valid order of the left sub-tree and one valid order of the right subtree. Put them together into an array with all the items from the left sub-tree at the beginning, and all those from the right sub-tree at the end. For demonstration, let's assume the tree also contained an A (as a descendant of the B you show). In an array, our data from our sub-trees would look like:

B A P H Z D

然后，我们从来自左子树中的最后一个项目开始，和走每在阵列向右，每次生成新的排列：

Then we start from the last item from the left sub-tree, and "walk" each across the array to the right, generating a new permutation each time:

B P A H Z D
P B A H Z D
B P H A Z D
P B H A Z D
P H B A Z D
[ ... ]    

对于左子树的每个有效订单，你需要做的所有这些的交错与右子树的每个有效订单（并将其返回到父，这将这样做）。

For each valid order of the left sub-tree, you need to do all these interleavings with each valid order of the right sub-tree (and return it to the parent, which will do the same).

这篇关于BST的输入可能的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！