Wie füge ich zwei BST in Java zusammen?

Question

Ich muss zwei BSTs zusammenführen. Wenn die angegebene Symboltabelle Schlüssel enthält, die bereits in dieser Symboltabelle enthalten sind, werden die Werte dieser Schlüssel durch die Werte in der angegebenen Symboltabelle überschrieben. aber ich bin völlig verloren von dem, was ich anfangen soll. Alles was ich gerade habe ist der Basisfall.

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

Nun, ich werde nicht den Code für dieses Problem schreiben. Ich kann Ihnen mit der Logik helfen, die erforderlich ist, um dieses Problem zu lösen, wenn Sie die Inorder-Traversierung einer BST durchführen und jedes Node-Objekt in einem Array speichern, wird das resultierende Array immer sortiert.

Schritt 1:

so, was Sie hier tun müssen, ist der Inorder Traversal des ersten Baums auszuführen und zu speichern, jedes Element in ar1 (array1). Machen Sie dasselbe für den zweiten Baum und speichern Sie seine Elemente in ar2 (array2).

Schritt 2:

verschmelzen die beiden sortierten Arrays Ar1 und Ar2 in AR3.

step3: konvertieren Sie jetzt dieses sortierte Array in eine BST und Sie sind fertig. aber die Frage ist Wie willst du das tun? Nun, es ist ziemlich einfach. hier kommt wieder die Traversierung ins Spiel.

1.Say Mitte ist das mittlere Element im Array.

2.Recursively konstruieren linken Unterbaum von Anfang bis Mitte der 1

3.Make das mittlere Element als Wurzel und weisen den linken Unterbaum zu.

4.Recurseconstruct rechten Teilbaum von Mitte + 1 bis Ende.

5.Zuordnen Sie den rechten Teilbaum zu root.

Werfen Sie einen Blick auf diesen Link Ihre Frage ist nur eine modifizierte Version der Frage hier gegeben. sortedlistToBst