Binäre Bäume in C: Eine vollständige Anleitung für Anfänger

Informatec Digital » Algorithmen » Binärbäume in C: Ein vollständiger Leitfaden für Anfänger

Willkommen zu diesem umfassenden Leitfaden zu Binärbäumen in C. In diesem Artikel werden wir die Grundlagen von Binärbäumen und ihre Implementierung in der Programmiersprache C untersuchen. Wenn Sie Programmieranfänger sind oder einfach nur Ihre C-Kenntnisse verbessern möchten, ist dieser Leitfaden genau das Richtige für Sie.

Binärbäume sind grundlegende Datenstrukturen in der Informatik und finden in einer Vielzahl von Anwendungen Verwendung. Das Verständnis ihrer Funktionsweise und Implementierung hilft Ihnen, komplexe Probleme effizienter und eleganter zu lösen.

In diesem Artikel behandeln wir die Grundlagen von Binärbäumen, darunter ihre Struktur, das Einfügen und Löschen von Knoten, das Durchlaufen des Baums und die Elementsuche. Wir stellen Ihnen außerdem praktische Beispiele in der Programmiersprache C vor , damit Sie sehen können, wie diese Konzepte in der Praxis angewendet werden.

Also lasst uns anfangen!

Was sind Binärbäume?

Binärbäume sind hierarchische Datenstrukturen, die aus miteinander verbundenen Knoten bestehen. Jeder Knoten kann bis zu zwei untergeordnete Knoten haben: einen auf der linken und einen auf der rechten Seite. Diese Zweizweigstruktur unterscheidet Binärbäume von anderen Datenstrukturen.

In einem binären Baum wird der erste Knoten als Wurzelknoten bezeichnet. Untergeordnete Knoten werden als Kindknoten bezeichnet, und Knoten ohne untergeordnete Knoten werden als Blattknoten bezeichnet. Knoten auf derselben Ebene werden Geschwisterknoten genannt.

Vorteile von Binärbäumen

Binäre Bäume bieten mehrere Vorteile hinsichtlich effizienter Datenspeicherung und -suche. Zu den wichtigsten Vorteilen gehören:

1. effiziente SucheBinäre Bäume ermöglichen eine schnellere Suche nach Elementen zur Laufzeit als andere Datenstrukturen, beispielsweise verknüpfte Listen. Dies liegt an der hierarchischen Struktur des Baums und seiner Fähigkeit, den Datensatz schnell zu partitionieren.
2. Flexibles Einsetzen und EntnehmenBinärbäume lassen sich sehr gut an Operationen zum Einfügen und Löschen von Knoten anpassen. Im Gegensatz zu statischen Datenstrukturen wie Arrays können Binärbäume dynamisch wachsen und ihre Struktur ändern.
3. Darstellung hierarchischer BeziehungenBinäre Bäume sind besonders nützlich für die Darstellung hierarchischer Beziehungen zwischen Elementen. Beispielsweise kann in einer Dateiverzeichnisstruktur jedes Verzeichnis als Knoten im Baum dargestellt werden, mit Unterverzeichnissen und Dateien als seinen untergeordneten Knoten.

Struktur eines Binärbaums

Bevor wir uns in die Implementierung von Binärbäumen in C vertiefen, ist es wichtig, ihre grundlegende Struktur zu verstehen. Jeder Knoten in einem Binärbaum enthält einen Wert und Verweise auf seine linken und rechten untergeordneten Knoten (sofern vorhanden).

Die folgende Tabelle zeigt die Struktur eines Knotens in einem Binärbaum:

Binärer Knoten
Wert
Linker Knoten
Rechter Knoten

Jeder Knoten kann beliebige Datentypen speichern, etwa ganze Zahlen, Zeichen oder komplexere Strukturen. Der Wurzelknoten ist der Ausgangspunkt des Baums und von ihm aus können wir auf alle anderen Knoten zugreifen.

Implementieren von Binärbäumen in C

Nachdem wir nun die Grundlagen von Binärbäumen verstanden haben, ist es an der Zeit, sie in der Programmiersprache C zu implementieren . Im Folgenden werden wir sehen, wie man eine Binärbaumstruktur in C deklariert und verwendet.

Deklarieren der binären Baumstruktur

In C können wir die Struktur eines Binärbaums mithilfe einer Struktur und Zeigern deklarieren. Hier ist die grundlegende Deklaration der Struktur:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

In dieser Struktur valor stellt den im Knoten gespeicherten Wert dar und izquierdo y derecho sind Zeiger auf die linken bzw. rechten untergeordneten Knoten.

Einen neuen Knoten erstellen

Um einen neuen Knoten im Binärbaum zu erstellen, müssen wir Speicher für den Knoten zuordnen und seine Werte festlegen. Hier ist eine C-Funktion, die einen neuen Knoten erstellt:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

Die Funktion malloc Es wird verwendet, um dem Knoten dynamischen Speicher zuzuweisen. Anschließend legen wir die Knotenwerte fest und geben den erstellten Knoten zurück.

Einfügen von Knoten

Das Einfügen von Knoten ist ein grundlegender Prozess in binären Bäumen. Ermöglicht Ihnen, dem Baum basierend auf dem Knotenwert an der richtigen Position neue Elemente hinzuzufügen. Unten sehen Sie eine C-Funktion zum Einfügen eines Knotens in einen Binärbaum:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Diese Funktion erhält einen Zeiger auf die Wurzel des Baums und den Wert des einzufügenden Knotens. Wenn root null ist, bedeutet dies, dass der Baum leer ist und wir einen neuen Knoten an der Wurzel erstellen. Andernfalls vergleichen wir den Wert des Knotens mit dem Wert der Wurzel und entscheiden, ob der Knoten links oder rechts eingefügt werden soll.

Löschen von Knoten

Das Löschen von Knoten in einem Binärbaum kann etwas komplexer sein. Dies hängt von mehreren Faktoren ab, beispielsweise davon, ob der zu löschende Knoten untergeordnete Knoten hat oder nicht. Unten sehen Sie eine C-Funktion zum Löschen eines Knotens in einem Binärbaum:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

In dieser Funktion prüfen wir, ob der Wert des Knotens kleiner, größer oder gleich dem Wert der aktuellen Wurzel ist. Je nach Fall führen wir folgende Aktionen durch:

• Wenn der Wert kleiner ist, gehen wir nach links im Baum.
• Wenn der Wert größer ist, gehen wir nach rechts im Baum.
• Wenn der Wert gleich ist, finden wir den nächsten Nachfolger des Knotens (den kleinsten Knoten im rechten Teilbaum) und ersetzen ihn durch den aktuellen Knoten. Dann entfernen wir den Nachfolger aus dem rechten Teilbaum.

Durchquerungen in binären Bäumen

Durchquerungen sind Operationen, die es uns ermöglichen, alle Knoten eines binären Baums in einer bestimmten Reihenfolge zu besuchen. Es gibt drei gängige Tourtypen:

In-Order-Traversierung : Zuerst wird der linke Teilbaum, dann der aktuelle Knoten und schließlich der rechte Teilbaum durchlaufen. Hier ist eine C-Funktion, die eine In-Order-Traversierung eines Binärbaums durchführt:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Preorder-Traversierung : Besucht zuerst den aktuellen Knoten, dann den linken Teilbaum und schließlich den rechten Teilbaum. Hier ist eine C-Funktion, die eine Preorder-Traversierung eines Binärbaums durchführt:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Postorder-Traversierung : Besucht zuerst den linken Teilbaum, dann den rechten Teilbaum und schließlich den aktuellen Knoten. Hier ist eine C-Funktion, die eine Postorder-Traversierung eines Binärbaums durchführt:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Suche nach Elementen

Die Suche nach Elementen in einem Binärbaum ermöglicht es uns, schnell einen bestimmten Wert innerhalb der Datenstruktur zu finden. Hier ist eine C-Funktion zum Suchen nach einem Element in einem Binärbaum:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Diese Funktion führt eine rekursive Suche im Binärbaum durch. Wenn der Wert des aktuellen Knotens mit dem gesuchten Wert übereinstimmt, wird der Knoten zurückgegeben. Andernfalls wird basierend auf dem Wert der linke oder rechte Teilbaum durchsucht und der Vorgang wiederholt, bis der Wert gefunden oder ein Nullknoten erreicht wird.

Beispiele für die Implementierung binärer Bäume in C

Nachdem wir nun die Grundlagen binärer Bäume und ihre Implementierung in C behandelt haben, schauen wir uns einige praktische Beispiele an.

Beispiel 1: Erstellen eines Binärbaums

Angenommen, wir möchten einen Binärbaum mit den folgenden Werten erstellen: 10, 5, 15, 3, 7, 13, 18. So können wir das in C machen:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

In diesem Beispiel erstellen wir einen Zeiger auf die Wurzel des Baums und verwenden dann die Funktion insertarNodo um die Werte dem Baum hinzuzufügen.

Beispiel 2: In-Order-Traversierung des Binärbaums

Um die Werte des Binärbaums der Reihe nach auszudrucken, können wir die Funktion aufrufen inOrden aus sicherer manera:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Dieses Beispiel druckt die Werte im Baum in aufsteigender Reihenfolge.

Häufig gestellte Fragen

1. Was ist der Unterschied zwischen einem binären Baum und einem binären Suchbaum?

Ein binärer Suchbaum (BST) ist ein spezieller Typ eines binären Baums, bei dem die Elemente so angeordnet sind, dass kleinere Werte links und größere Werte rechts stehen. Dies ermöglicht eine effizientere Suche nach Elementen im Vergleich zu einem herkömmlichen Binärbaum.

2. Kann ich in einem Binärbaum Knoten mit doppelten Werten haben?

Ja, es ist möglich, dass in einem Binärbaum Knoten mit doppelten Werten vorhanden sind. Allerdings kann es je nach Implementierung und den spezifischen Regeln des Binärbaums unterschiedliche Möglichkeiten geben, mit doppelten Knoten umzugehen. Einige Implementierungen erlauben möglicherweise Duplikate und speichern sie in beliebiger Reihenfolge, während andere möglicherweise erfordern, dass doppelte Werte speziell behandelt oder verworfen werden.

3. Wie kann ich einen bestimmten Knoten aus einem Binärbaum entfernen?

Um einen bestimmten Knoten aus einem Binärbaum zu entfernen, müssen Sie die folgenden Schritte ausführen:

1. Suchen Sie mithilfe einer Baumsuche nach dem Knoten, den Sie löschen möchten.
2. Betrachten Sie die verschiedenen Fälle der Eliminierung:
   • Wenn der Knoten keine untergeordneten Knoten hat, können Sie ihn einfach löschen und seinen Speicher freigeben.
   • Wenn der Knoten nur ein untergeordnetes Element hat, können Sie den Knoten durch sein untergeordnetes Element ersetzen.
   • Wenn der Knoten zwei untergeordnete Knoten hat, müssen Sie den nächsten Nachfolger (den kleinsten Knoten im rechten Teilbaum) finden und den Wert des zu löschenden Knotens durch den Wert des Nachfolgers ersetzen. Entfernen Sie anschließend den Nachfolger aus dem Baum.
3. Passt Links und Zeiger nach Bedarf an, um die richtige Baumstruktur beizubehalten.

4. Was ist ein vollständiger Binärbaum?

Ein vollständiger Binärbaum ist ein spezieller Typ eines Binärbaums, bei dem alle Ebenen, außer möglicherweise der letzten, vollständig ausgefüllt sind und die Knoten der letzten Ebene möglichst weit links liegen. Dies bedeutet, dass alle Knoten zwei untergeordnete Knoten haben, mit Ausnahme möglicherweise der Knoten auf der letzten Ebene, die ein oder kein untergeordnetes Element haben können.

5. Wie hoch ist ein Binärbaum?

Die Höhe eines binären Baums ist die Länge des längsten Pfades von der Wurzel zu einem Blatt. Mit anderen Worten ist es die maximale Anzahl von Kanten zwischen der Wurzel und jedem Blatt im Baum. Die Höhe wird anhand der Anzahl der Ebenen gemessen. Ein Baum mit nur einem Knoten hat also eine Höhe von 0 und ein leerer Baum hat keine Höhe.

6. Wann sollte ich in meinen Programmen einen Binärbaum verwenden?

Binärbäume sind in vielen Situationen nützlich. Einige gängige Fälle, in denen Sie Binärbäume verwenden könnten, sind:

• Effiziente Elementsuche: Wenn Sie schnell Elemente in einer Datenstruktur nachschlagen müssen, kann ein Binärbaum einen effizienten Zugriff auf die Daten bieten.
• Darstellung hierarchischer Beziehungen: Binäre Bäume eignen sich ideal zur Darstellung hierarchischer Beziehungen, wie z. B. der Verzeichnisstruktur in einem Dateisystem.
• Datensortierung: Sie können binäre Suchbäume verwenden, um Daten effizient zu sortieren und Suchvorgänge, Einfügungen und Löschungen in logarithmischer Zeit durchzuführen.

Denken Sie daran, Ihre Anforderungen zu bewerten und die Komplexität der Operationen an Binärbäumen zu berücksichtigen, bevor Sie sich für deren Verwendung in Ihren Programmen entscheiden.

Fazit

In diesem umfassenden Leitfaden haben wir die grundlegenden Konzepte binärer Bäume in C erkundet. Wir haben ihre Struktur kennengelernt, erfahren, wie man Knoten einfügt und entfernt, Durchläufe durchführt und nach Elementen in einem binären Baum sucht.

Wir hoffen, dass Ihnen dieser Leitfaden ein solides Verständnis von Binärbäumen und ihrer Implementierung in C vermittelt hat. Binärbäume sind vielseitige und leistungsstarke Datenstrukturen, die Ihnen bei der Lösung einer breiten Palette von Programmierproblemen helfen können.

Denken Sie daran, mit den bereitgestellten Beispielen zu üben und zu experimentieren, um Ihr Verständnis von Binärbäumen in C zu vertiefen. Viel Erfolg auf Ihrem Weg zum Erlernen und Entwickeln von Software!