Javaで2つのBSTをマージする方法は？

Question

2つの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 
} 

Answer 1

よくこの問題のコードを書きません。この問題を解決するために必要なロジックをお手伝いします。

BSTのインオーダートラバーサルを論理的に考えると、各Nodeオブジェクトを配列に格納すると、結果の配列は常にソートされます。

STEP1：

ので、あなたがここで何をする必要があるか最初の木のINORDERトラバーサルを実行し、AR1内の各要素（配列1）を格納しています。 2番目のツリーで同じことを行い、その要素をar2（array2）に格納します。

STEP2：

は、2つのソートされた配列がAR3にAr 1及びAr 2合流。

STEP3： 今BSTには、このソートされた配列を変換し、設定が完了しています。しかし、質問は どのようにそれを行うつもりですか？よくそれは非常に簡単です。 inorder traversalが再びここに現れます。

1.Say半ばには、配列の中央の要素です。

2.Recursivelyルートとして中間要素3.Make開始から半ば1

に、左の部分木を構築し、それを左サブツリーを割り当てます。

4.Recursivelyは最後まで半ば+ 1からの右部分木を構築します。

5.Assignルートに右のサブツリー。

は、あなたの質問がここに与えられた問題のほんの修正版では、このリンクを見てみましょう。 sortedlistToBst