Die kurze Antwort lautet: du kannst es nicht. Ein BST erfordert, dass die Knoten der Regel folgen: links <= aktuell < rechts. In dem Beispiel, auf das du verwiesen hast: http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg, wirst du feststellen, dass du keinen BST mit der gleichen Form bauen kannst.
Wenn du jedoch die Definition eines BST so dehnen möchtest, dass sie links <= aktuell <= rechts zulässt (beachte, dass hier aktuell <= rechts erlaubt ist, im Gegensatz zur strengeren Definition), kannst du das tun. Sortiere alle Elemente und füge sie in ein Array ein. Führe nun eine In-Order-Traversierung durch und ersetze die Werte an den Knoten mit jedem Element in deinem Array. Hier ist ein Pseudocode:
// t ist dein nicht-BST-Baum, a ist ein Array, das die sortierten Elemente von t enthält, i ist der aktuelle Index in a
Index i = 0
create_bst(Tree t, Array a)
{
if(t ist NIL)
return;
create_bst(t->left, a)
t->data = a[i]
i++
create_bst(t->right, a)
}
Das Ergebnis wird jedoch kein echter BST sein. Wenn du einen echten BST haben möchtest, der so nah wie möglich an der originalen Form ist, dann füge die Elemente erneut in einem sortierten Array ein, aber füge sie dieses Mal in einen BST ein. Die Reihenfolge, in der du sie einfügst, wird durch die Größen der Teilbäume des Originalbaums definiert. Hier ist ein Pseudocode:
// links wird zu Beginn auf 0 gesetzt
create_true_bst(Tree t, BST bt, Array a, Index links)
{
Index i = links + größe_von_linkem_teilbaum(t)
bt->einfügen(a[i])
if (größe_von_linkem_teilbaum(t) != 0)
{
create_true_bst(t->left, bt, a, links)
create_true_bst(t->right, bt, a, i + 1)
}
}
Dies garantiert jedoch nicht, dass die Form gleich ist.
