Einfügen eines Knoten in binären Suchbaum

Ziel ist es die Ordnung eines binären Suchbaums nicht zu zerstören. Beispiel für Implementierung in Java:

public class EinfuegenBinaererSuchbaum

{

public BNode insert(Object obj)

{

// Beginne bei der Wurzel

return insert(obj, root);

}

// Bemerke unsere Insert-Methode ist eine

// return-Methode vom Typ BNode

public BNode insert(Object obj, BNode a)

{

if(a == null)

{

//Füge neuen Knoten ein

a = new BNode(obj);

}

else if( obj < a.getdata()

{

//Suche im linken Teilbaum

BNode t = insert(obj, a.getLeft()),

a.setLeft(t);

}

else if(obj > a.getData())

{

BNode t = insert(obj, a.getRight());

a.setRight(t);

}

else

{

print “Duplicate!”;

}

return a;

}

}