algorithm - BST 输入的可能排列

Question

我得到一个字符串，即“CPHBDZ”。通过向 BST 插入（按此顺序）字母，我将拥有：

  C
 / \
B   P
   / \
  H   Z
 /
D

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

Answer 1

假设您没有进行任何旋转（等）来平衡树，您可以从树的结构中得出答案：新节点始终作为现有节点的后代添加，因此树中更高的任何节点都必须先于它自己的后代，但可以与它的“同行”（任何既不是它的父母也不是后代的东西）随意重新排列。

例如，由于您有C作为树的根，因此C必须是从流中读取的第一项。由于它的后代是B和P，输入中的下一个项目必须是这两个之一。B没有任何后代，但P有两个:H和Z，因此它们必须在 之后阅读P，但可以相对于B. 同样，对于andZ可以按任何顺序排列，但必须在 之前。HDHD

编辑：至于生成所有这些排列，一种简单的（作弊）方法是使用 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
[ ... ]    

对于左子树的每个有效顺序，您需要对右子树的每个有效顺序进行所有这些交织（并将其返回给父级，父级也会这样做）。

Answer 2

在 Python 中，

tree = {
    'C' : ['B', 'P'],
    'P' : ['H','Z'],
    'H' : ['D']}

def f(tree,  ready):
    if not ready:
        return [[]]
    else:
        rv = []
        for r in ready:
            for rest in f(tree,
                          [n for n in ready if r != n] + tree.get(r, [])):
               rv.append([r] + rest)
        return rv

for o in f(tree, 'C'):
    print ''.join(o)