二叉搜索樹相交

Question

我有2個二叉搜索樹T1和T2，節點數n> = 1。對於每個節點P，我們有節點和KEY（P）之間的鏈接的LEFT（P）和RIGHT（P）對於節點的價值。 T1的根是R1，T2的根是R2。 我需要一個線性算法，它將確定在T1和T2中都可以找到的值。

我的想法到現在爲止是做T1的序遍歷和T2搜索當前元素，像這樣：

inorder(node) 
    if node is not NULL 
     inorder(LEFT(node)) 
     if find(KEY(node), R2) 
      print KEY(node) 
     inorder(RIGHT(node)) 

凡find(KEY(node), R2)落實在樹T2 KEY（節點）的二進制搜索。

這是正確的解決方案嗎？這是一個線性算法嗎？ （我知道遍歷是O（n）複雜度）。或者，還有另一種方法來交叉2個二叉搜索樹？

謝謝！

Answer 1

您使用遞歸執行任務的當前inorder遍歷。這使得難以同時運行多個。

因此，首先我會重新編寫使用顯式堆棧的方法（example here in C#）。現在，複製所有的狀態，以便我們同時執行遍歷樹和樹。我們比較他們的KEY()值。如果它們是不等於那麼我們繼續遍歷樹的值低於KEY()的值。

如果兩個值是相等的，那麼，我們該屈服值，再繼續穿越都樹木。

這與合併兩個已排序序列的概念類似 - 我們需要做的就是檢查每個序列產生的「下一個」值，產生兩個值中較低的值，然後按該序列向前移動。

---

在回答您的原始提案：

這是一個線性算法？

號爲您在序遍歷，你打電話find這是O(log n)參觀過程中的每一個節點。所以你的完整算法是（如果我正確記得複雜性）O(n log n)。