比較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

回答