BST输入的可能排列

Question

给我一个字符串,即"CPHBDZ".通过(按此顺序)将字母插入BST,我将:

  C
 / \
B   P
   / \
  H   Z
 /
D

如果我们将字符串的顺序更改为"CBPHDZ",我们将得到相同的树.我必须找到并列出提供相同BST的输入字符串的所有排列.我想出了如何计算这些排列的数量,但我无法弄清楚实际找到它们的任何算法.

Answer 1

假设您没有进行任何轮换(等)来平衡树,您可以从树的结构中获得答案:新节点总是作为现有节点的后代添加,因此树中较高的任何节点必须位于树的前面.它自己的后代,但可以随意重新安排它的"同伴"(任何既不是它的父母也不是后代).

例如,由于您具有C树的根,因此C必须是从流中读取的第一个项.由于它的后代是B和P,输入中的下一个项目必须是这两个中的一个.B没有任何后裔,但P有两个:H和Z,所以他们不得不后读P,但可以在任何顺序相对于B.同样地,Z可以在相对于任何顺序H和D,但H必须先D.

编辑:至于生成所有这些排列,一种简单(作弊)的方式是使用Prolog.基本上,您将依赖关系编码为"事实",并且它将生成适合这些事实的所有排列.事实上(没有双关语意),这几乎就是对Prolog所做的事情的描述.

你自己做,你可能想要递归地完成大部分工作.有效排序是根,后跟其后代的有效顺序的任何交错.

至于如何进行交织,您将(例如)生成左子树的一个有效顺序和右子树的一个有效顺序.将它们放在一个数组中,其中包含开头左侧子树中的所有项目,以及最后右侧子树中的所有项目.为了演示,让我们假设树也包含一个A(作为B你展示的后代).在数组中,来自子树的数据如下所示:

B A P H Z D

然后我们从左子树中的最后一个项开始,并在每个数组中向右"走",每次生成一个新的排列:

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
[ ... ]    

对于左子树的每个有效顺序,您需要使用右子树的每个有效顺序执行所有这些交错(并将其返回到父级,这将执行相同的操作).