6

我得到一个字符串,即“CPHBDZ”。通过向 BST 插入(按此顺序)字母,我将拥有:

  C
 / \
B   P
   / \
  H   Z
 /
D

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

4

2 回答 2

6

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

例如,由于您有C作为树的根,因此C必须是从流中读取的第一项。由于它的后代是BP,输入中的下一个项目必须是这两个之一。B没有任何后代,但P有两个:HZ,因此它们必须在 之后阅读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
[ ... ]    

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

于 2012-11-20T17:03:45.113 回答
3

在 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)
于 2012-11-20T20:09:26.863 回答