假设我有以下信息：
_____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（根）开始。我有两个或更多的孩子吗？在这种情况下，是的，3:
T，L，X。比较
T、L和X的子树。T、L和X的子树集在整个级别的范围内是否相同？在这种情况下，是的，它一直都是W的在上面的第二棵树中，答案是否定的，因为这会把事情搞砸。现在下拉到
A B的子级、Q、W和T。重复上述步骤。是否有两个或更多的孩子？是的，L和X他们有孩子吗？在上面的例子中，没有，所以没什么可做的了但是想象一下T和A是整个子树，有孩子、孙子等等。现在的问题是：这些子树在B范围内的整个层次上是否相同？那么A的子树集是否与B的子树集相同？ 最佳答案
注意：对等式检查短路的声明比枚举策略需要测试的“效率高得多”如果你的输入集不是很大，那就不太可能有什么不同，如果它很大，那么你可能需要用有代表性的数据来衡量。
也就是说，这是一个算法的伪代码，该算法从左到右比较所有子树，尝试跨树逐个查看元素，而不是预先生成所有集合：
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()
我在这里所做的只是检查每个子树中的每个标签是否相等，诀窍在于我使用的迭代器不是具体化标签集，而是有效地执行每个子树的前序遍历。您当然可以使用您想要的任何其他懒树节点枚举方法。
注意两件事：首先，这个遍历不是您想要的级别顺序遍历。相反，它是一个预排序遍历；如果使用级别顺序遍历真的很重要，那么您需要用一个以这种方式枚举的迭代器替换我上面编写的迭代器其次，如前所述，该算法不检查结构等式，只检查顺序遍历等式。如果重要的话，这很容易解决。
关于java - 算法:跨树级别识别重复的子集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19237111/