java - 算法:识别跨树级别的重复子集

Question

假设我有以下内容:

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

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

更笼统地说，我希望能够从树的根部开始，查看我 child 的子树集(本质上是孙子树集)，并确定它们是否完全相同穿过树级别，然后递归到我的 children ，并在他们的每个较小的范围内做同样的事情。冲洗，重复，一直冲洗到整棵树的底部。

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

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

能够获取第一个 A，然后是 Q，意识到它们不相同并且没有意义继续搜索，然后短路。

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

(我还用“Java”标签标记了这个问题，只是因为我实际实现了这个树结构[以及我正在应用的其他算法并且没有有 Unresolved 问题]发生使用那种语言。我也可以翻译伪代码。)

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

• 从W(根)开始。
• 我有 2 个或更多 child 吗？在这种情况下，是的，3:T、L、X。
• 比较 T、L 和 X 的子树。
• T、L 和X 的子树集在整个 中是否相同> 级别 在 W 的范围内？在这种情况下，是的，它一直都是 A B。在上面的第二棵树中，答案是否定的，因为 Q 把事情搞砸了。
• 现在下拉到 W 的子级 T、L 和 X。从上面重复前面的步骤。 T 是否有 2 个或更多 child ？是的，A 和 B。他们有 child 吗？在上面的例子中，没有，所以没有什么可做的了。但是想象一下 A 和 B 是完整的子树，有子树、孙子等等。现在的问题是:这些子树在 中是否相同整个 级别在T 的范围？那么A son of T的子树集合是否与B son of T的子树集合相同？

Answer 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()

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

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