In einen Suchbaum einfügen

Wer einen neuen Wert einfügt, sucht ihn zuerst. Die erfolglose Suche endet an einem leeren Baum — genau dort ist sein Platz.

• Einfügen:wie beim Suchen von der Wurzel absteigen: kleiner → links, größer → rechts.
• Leerer Baum erreicht:Der neue Wert wird dort als Blatt eingesetzt. Kein anderer Knoten verschiebt sich.
• Wert schon vorhanden:Die Suche endet mit „gefunden“ — es wird nichts eingefügt.
• Form hängt von der Reihenfolge ab:Dieselben Werte ergeben je nach Einfügereihenfolge einen buschigen oder einen langen, dünnen Baum.
• Höhe messen:Die Höhe entscheidet über den Aufwand jeder späteren Suche.

Füge die sieben Schlüssel mit ▶ oder „Schritt“ ein. Lege danach das Lineal an: Ziehe den Schieber rechts (oder ↑/↓) auf die unterste Ebene und trage den Messwert ein. Vergleiche die drei Reihenfolgen in der Messtabelle.

Halte fest: Neue Werte landen immer als Blatt am Ende eines Suchpfads. Sortiert eingefügt entartet der Baum zur Liste — Höhe 7 statt 3 bei denselben sieben Werten.

Nach den Ergänzenden Hinweisen 2025 bekommt ein leerer Baum bei setItem(x) automatisch zwei leere Teilbäume. Das macht die Methode kurz.

static void einfuegen(BinTree<Integer> b, int x) {
    if (b.isEmpty()) {
        b.setItem(x);                          // leerer Baum wird zum Blatt
    } else if (x < b.getItem()) {
        einfuegen(b.getLeft(), x);             // links weiter
    } else if (x > b.getItem()) {
        einfuegen(b.getRight(), x);            // rechts weiter
    }                                          // x schon da: nichts tun
}

BinTree<Integer> baum = new BinTree<Integer>();
int[] werte = {50, 30, 70, 20, 40};
for (int w : werte) {
    einfuegen(baum, w);
}
System.out.println(baum.getLeft().getRight().getItem());   // 40

• Teilbaum weiterreichen:getLeft() liefert den Teilbaum selbst, keine Kopie — was die Rekursion dort einsetzt, hängt danach im Baum.
• Sortieren:Alle Werte einfügen und danach inorder ausgeben liefert sie aufsteigend sortiert.