我得到一个字符串,即“CPHBDZ”。通过向 BST 插入(按此顺序)字母,我将拥有:
C
/ \
B P
/ \
H Z
/
D
如果我们将字符串的顺序更改为“CBPHDZ”,我们将得到相同的树。而且我必须找到并列出提供相同 BST 的输入字符串的所有排列。我想出了如何计算这些排列的数量,但我无法弄清楚任何实际找到它们的算法。
我得到一个字符串,即“CPHBDZ”。通过向 BST 插入(按此顺序)字母,我将拥有:
C
/ \
B P
/ \
H Z
/
D
如果我们将字符串的顺序更改为“CBPHDZ”,我们将得到相同的树。而且我必须找到并列出提供相同 BST 的输入字符串的所有排列。我想出了如何计算这些排列的数量,但我无法弄清楚任何实际找到它们的算法。
假设您没有进行任何旋转(等)来平衡树,您可以从树的结构中得出答案:新节点始终作为现有节点的后代添加,因此树中更高的任何节点都必须先于它自己的后代,但可以与它的“同行”(任何既不是它的父母也不是后代的东西)随意重新排列。
例如,由于您有C
作为树的根,因此C
必须是从流中读取的第一项。由于它的后代是B
和P
,输入中的下一个项目必须是这两个之一。B
没有任何后代,但P
有两个:H
和Z
,因此它们必须在 之后阅读P
,但可以相对于B
. 同样,对于andZ
可以按任何顺序排列,但必须在 之前。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
[ ... ]
对于左子树的每个有效顺序,您需要对右子树的每个有效顺序进行所有这些交织(并将其返回给父级,父级也会这样做)。
在 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)