java - 比较 2 个 b 树以查看它们是否包含相同的值

Question

看到 2 个 b 树可能具有相同的值，但形状不同，是否有一种算法可以遍历这些值并比较两棵树是否具有相同的键？

重点是如果它们包含不同的 key (尽快)，则能够摆脱困境。

我猜除非您同时在两个 b 树中执行查找，否则递归算法可能无法工作。

我见过遍历 B 树的算法，但我不想遍历两者，然后比较 key ，我想要一些更智能的东西，如果有差异，它会尽快退出。

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

Answer 1

基本技术是以某种方式拥有一个表示中序遍历中当前点的对象。一旦你有了其中两个，一个用于树的每个实例，你就可以继续为下一个键抽取它们，当两个键第一次返回不同的下一个键时，你就完成了。

在 C# 中，您将使用 yield return 进行遍历，一次产生一个键，并跟踪它在树中的位置。然后，您可以将其中两个传递给 SequenceEquals，它会在遇到第一个差异时立即退出。在 Java 中，您必须自己构建该机制，但这并不难。