比较2棵树看它们是否包含相同的值

看到2棵树可能具有相同的值，但形状不同，是否有一种算法可以通过这些值并比较两棵树是否具有相同的密钥？比较2棵树看它们是否包含相同的值

重点是如果他们包含不同的密钥（尽快）能够救助。

递归算法可能不会工作，除非你在同一时间在两个b-tree中进行查找。

我见过遍历B树的算法，但我不想遍历两者，然后比较键，我想要更聪明的东西，如果有差异就会尽早释放。

基本上该函数返回true/false。

2013-01-31 loyalflow

基本技术是以某种方式有一个对象，该对象表示按顺序遍历中的当前点。一旦你有两个这样的树，每一个树的实例一个，你只需要继续抽取下一个键，然后第一次返回不同的下一个键，就完成了。

在C＃中，您将使用yield return进行遍历，一次只产生一个键，并跟踪它在树中的位置。然后你可以将其中的两个传递给SequenceEquals，一旦遇到第一个区别，它就会立即释放。在Java中，您必须自己构建该机制，但这并不难。

2013-01-31 14:53:59

问题是**如何迭代**。例如，在DFS中迭代都不太可能产生正确的结果。在二叉树中，您需要按顺序遍历，并按顺序迭代两个二叉树。在B-Tree中，我应该对其进行一些修改。 – amit

@amit：对不起，我对你的评论感到困惑。 DFS是* search *技术，而不是*遍历*技术。显然你需要一个顺序遍历;后期订购或预购遍历不会做正确的事情。我没有看到与搜索特定项目的树有什么关系。 –

注意因为你多于一个孩子（回想起在二叉树中“按顺序”是因为它在遍历右边的儿子和遍历左边的儿子之前），所以有序遍历也可以在B-树中变化。将它修改为B树不是一个大问题，但对于那些不熟悉该技术的人来说，这可能并不是微不足道的。显然，我的意思是预购，而不是DFS，对于混淆感到抱歉。 – amit

假设你的意思是b-tree那么你需要做的就是一次迭代两次。任何迭代器之间的任何偏差都会证明它们的内容不同。在构建树时不会发现更好的算法，而不会收集更多细节。

如果你不是在谈论它被描述为b-tree：

... B树是保持数据整理，并允许搜索，顺序访问，插入树数据结构，并在对数时间删除。

那么你需要先对它进行排序然后遍历它。

2013-01-31 14:55:43 OldCurmudgeon

因此，我关于它是一个“B树”的警告，如在计算机科学中，B树是一个树数据结构，它保持数据的排序并允许在对数时间内进行搜索，顺序访问，插入和删除。它是内在排序的，所以按顺序迭代是微不足道的。 – OldCurmudgeon

我同意它可以完成，但它不是微不足道的。您需要修改二叉树的顺序遍历（'遍历（左），op（根），遍历（右）'）以使遍历遵循“排序”顺序。我同意这并不复杂，但对于不熟悉这种技术的人来说，这不是微不足道的。 – amit

回答