C Academy · Lektion

In einen BST einfügen

Erstellen Sie einen binären Suchbaum.

In einen BST einfügen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Die Sortierregel des BST

Ein Binärer Suchbaum (BST) ist ein Binärbaum mit einer zusätzlichen Regel: Für jeden Knoten sind alle Werte in seinem linken Teilbaum kleiner und alle Werte in seinem rechten Teilbaum größer.

Diese Sortierung ermöglicht es, in einer Zeitspanne proportional zur Höhe des Baums zu suchen, einzufügen und zu löschen.

Wo ein Wert hingehört

Zum Einfügen beginnen wir an der Wurzel und vergleichen. Ist der neue Wert kleiner, gehen wir nach links; ist er größer, gehen wir nach rechts.

Wir wiederholen dies, bis wir eine leere Stelle (NULL) erreichen. Genau dort gehört der neue Knoten hin.

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

Die create_node-Hilfsfunktion

Beim Einfügen werden neue Blattknoten erstellt. Daher verwenden wir einen Konstruktor wieder, der einen Knoten allokiert und initialisiert.

Beide Kinder beginnen mit NULL, da ein neu eingefügter Knoten immer ein Blatt ist.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

Rekursives Einfügen

Die sauberste Variante des Einfügens ist rekursiv und gibt die (möglicherweise neue) Wurzel des Teilbaums zurück.

Ist der Teilbaum leer, geben wir einen neuen Knoten zurück. Andernfalls rufen wir die Funktion rekursiv für den linken oder rechten Teilbaum auf, verknüpfen das Ergebnis erneut und geben anschließend die unveränderte Wurzel zurück.

Node *insert(Node *root, int value) {
    if (root == NULL)
        return create_node(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;  /* equal: ignore duplicate */
}

Warum die Wurzel zurückgegeben wird

Durch die Rückgabe der Teilbaumwurzel kann der Elternknoten die Verknüpfung in einer Zeile wiederherstellen: root->left = insert(root->left, v).

War der Teilbaum leer, wird der zurückgegebene neue Knoten zum Kind. War er nicht leer, wird dieselbe Wurzel zurückgegeben und die Verknüpfung bleibt unverändert.

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

Duplikate behandeln

Echte BSTs müssen festlegen, wie mit gleichen Werten umgegangen wird. Häufig werden Duplikate ignoriert, wie es unser insert tut, da für den Gleichheitsfall kein Zweig vorhanden ist.

Alternativen sind ein Zähler pro Knoten oder das konsequente Einfügen von Duplikaten auf einer Seite.

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

Einen BST aufbauen

Das Einfügen einer Wertesequenz erzeugt einen Baum, dessen Form von der Einfügereihenfolge abhängt.

Hier fügen wir mehrere Zahlen ein und geben die direkten Kinder der Wurzel aus, um zu bestätigen, dass die Sortierregel eingehalten wird.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return create_node(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}

int main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

Ein iteratives Einfügen

Sie können auch ohne Rekursion einfügen. Wir bewegen uns mit einem Pointer nach unten und merken uns den Elternknoten, bis wir eine leere Stelle finden.

Anschließend hängen wir den neuen Knoten an der richtigen Seite dieses Elternknotens ein.

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

Die Einfügereihenfolge formt den Baum

Das Einfügen von 1,2,3,4,5 in sortierter Reihenfolge erzeugt einen degenerierten Baum, der wie eine verkettete Liste aussieht und dessen Höhe der Anzahl der Knoten entspricht.

Eine Einfügereihenfolge, die den Baum ausbalanciert, hält die Höhe nahe bei log(n). Die Balance beeinflusst die Suchgeschwindigkeit direkt.

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

Kosten des Einfügens

Jedes Einfügen durchläuft einen Pfad von der Wurzel zu einem Blatt und benötigt daher eine Rechenzeit proportional zur Höhe des Baums.

Bei einem ausgeglichenen Baum sind das ungefähr log(n) Vergleiche, bei einem degenerierten Baum können es n sein. Deshalb gibt es selbstbalancierende Bäume.

Vollständige Einfügedemo

Dieses Programm fügt Werte ein und zählt anschließend die Knoten, um zu bestätigen, dass fünf verschiedene Werte gespeichert und ein Duplikat ignoriert wurden.

Das doppelte 10 erhöht die Anzahl nicht, weil insert gleiche Werte verwirft.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,10,20};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("count=%d\n", count(root));
    return 0;
}

Kurze Überprüfung

Denken Sie über das Einfügeverhalten nach.

Zusammenfassung

Beim Einfügen in einen BST wird der neue Wert mit jedem Knoten verglichen: Bei kleineren Werten geht es nach links, bei größeren nach rechts, bis eine leere Position gefunden wird.

Die rekursive Form gibt die Wurzel des Teilbaums zurück, damit der übergeordnete Knoten die Verknüpfungen sauber wiederherstellen kann. Die Kosten des Einfügens steigen mit der Höhe des Baums, daher spielt die Einfügereihenfolge eine wichtige Rolle.

Häufig gestellte Fragen

Ist die Lektion „In einen BST einfügen“ kostenlos?

Ja — der vollständige Text von „In einen BST einfügen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „In einen BST einfügen“?

Erstellen Sie einen binären Suchbaum. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „In einen BST einfügen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy