1

说我有以下内容：

   _____W_____
  |     |     |
 _T_   _L_   _X_
|   | |   | |   |
A   B A   B A   B

如您所见，它是一棵标准树（不是二叉树，事实证明它W有三个孩子）。我的目标是确定A B子序列在整个底层重复的事实。

更一般地说，我希望能够从树的根部开始，查看我的孩子的子子树集（本质上是孙子树集）并确定它们在整个树中是否相同水平，然后递归到我的孩子，并在每个较小的范围内做同样的事情。冲洗，重复，一直到整个树的底部。

我想到的一个简单的解决方案是对每个子树（在本例中为 、 和 ）进行广度优先（或深度优先）遍历T并L比较X我想出的单词（减去第一个字符）。在这种情况下，广度优先遍历会产生TAB,LAB和XAB，并且忽略第一个字符，我会看到它们都是AB. 但是想象一下，如果树是以下内容：

   _____W_____
  |     |     |
 _T_   _L_   _X_
|   | |   | |   |
A   B Q   B A   B

能够抓住第一个A，然后Q意识到它们是不一样的，并且继续搜索和短路是没有意义的，效率会高得多。

我主要是想看看是否有一些“明显”的算法可以在这里应用，或者，也许是为这个特定问题创建的算法；我从未见过、找不到和/或不知道如何搜索。

（我还用“Java”标签标记了这个问题，仅仅是因为我对这个树结构的实际实现[以及我正在应用的其他算法并且没有未回答的问题]恰好是用那种语言。我可以翻译伪代码，以及。）

编辑- 作为上面第一棵树上的一些示例步骤，这可能更有意义：

  • 从W（根）开始。
  • 我有 2 个或更多孩子吗？在这种情况下，是的，3: T, L, X。
  • 比较T、L和X的子子树。
  • 在' 范围内的整个级别上T，L、 和X' 的子子树集是否相同？在这种情况下，是的，它一直在跨越。在上面的第二棵树中，答案是否定的，因为这会把事情搞砸。WA BQ
  • 现在下拉到W的孩子、T、L和X。从上面重复前面的步骤。T有2个或更多的孩子吗？是的，A并且B。他们有孩子吗？在上面的例子中，没有，所以没有什么可做的。但是想象A和B是整个子树，有孩子、孙子等等。现在的问题是：这些子树在's 范围内的整个级别上是否相同？那么' 的子子树集与 ' 子子树的集相同吗？TA son of TB son of T
4

1 回答 1

1

注意：声称短路你的相等检查比枚举策略需要测试“更有效”。如果您的输入集不是很大，则不太可能有所作为，如果它很大，那么您可能需要使用代表性数据进行测量。

也就是说，这是一种算法的伪代码，该算法从左到右比较所有子树，尝试在树中一次查看一个元素，而不是预先生成所有集合：

function AllLeavesEqual(tree):
  if (tree.children.size < 2):
    return true
  subtreeIterators = [GetLeafIterator(t) for subtree in tree.children]
  baseLeaves = subtreeIterators[0]
  comparisonLeaves = subtreeIterators[1:]
  pop one item off of each iterator
  while (baseLeaves.hasNext()):
    nextLeaf = baseLeaves.next()
    for comparisonIterator in comparisonLeaves:
      if (!comparisonIterator.hasNext() or comparisonIterator.next() != nextLeaf):
        return false

  return true iff no iterator in comparisonLeaves satisfies iterator.hasNext()

function GetLabelIterator(tree):
  return Iterator:
    stack = Stack(tree)

    define next():
      t = Pop(stack)
      push each of t.children onto stack in reverse order
      return t.label

    define isEmpty():
      return stack.isEmpty()

我在这里所做的只是检查每个子树中的每个标签是否相等，诀窍是我使用迭代器而不是具体化标签集，它有效地执行每个子树的前序遍历懒惰。您当然可以使用您想要的任何其他惰性树节点枚举方法。

请注意两点：首先，此遍历不是您想要的级别顺序遍历。而是先序遍历；如果使用级别顺序遍历真的很重要，那么您需要将我上面编写的迭代器替换为以这种方式枚举的迭代器。其次，如上所述，该算法不检查结构相等性，仅检查有序遍历相等性。如果重要，这很容易解决。

于 2013-10-08T01:15:07.100 回答