如何合併java中的兩個BST？

我需要合併兩個BST。如果給定符號表包含已在此符號表中的鍵，則merge將用給定符號表中的值覆蓋這些鍵的值。但我完全失去了我想如何開始..我現在所擁有的只是基本情況。如何合併java中的兩個BST？

public class BST<Key extends Comparable<Key>, Value> { 
private Node root;    // root of BST 

private class Node { 
    private Key key;   // sorted by key 
    private Value val;   // associated data 
    private Node left, right; // left and right subtrees 

    public Node(Key key, Value val) { 
     this.key = key; 
     this.val = val; 
    } 


public void merge(BST bst) { 
    if(bst == null) return; 
    // TODO 
}

來源

2016-04-27 yenyen

好吧，我不會寫這個問題的代碼。我可以幫助你解決這個問題所需的邏輯

現在思考如果你執行BST的inorder遍歷並將每個Node對象存儲在一個數組中，結果數組將總是被排序。

第一步：

，所以你需要做的是在AR1（數組1）執行第一樹的序遍歷並存儲每個元素。對第二棵樹執行相同操作並將其元素存儲在ar2（array2）中。

step2：

將兩個排序後的數組ar1和ar2合併到ar3中。

step3：現在將這個已排序的數組轉換成BST，然後就完成了。但問題是你會怎麼做？這很簡單。在這裏，遍歷再次發揮作用。

1.Say mid是數組中的中間元素。

2.Recursively構建從開始左子樹到中等1

3.Make中間元件作爲根和左子樹分配給它。

4.從mid + 1遞歸構造右側子樹到結束。

5.將右側子樹分配給根。

看看這個鏈接你的問題只是這裏給出的問題的修改版本。 sortedlistToBst

來源

2016-05-01 20:59:10 batman007

如何合併java中的兩個BST？

回答

相關問題