Grundlagen von Binärbäumen: Struktur, Traversierung und Code

Trees (Bäume)

Eine nichtlineare Struktur, deren Knoten folgende Merkmale aufweisen:

• a) Die Zinsdifferenz zwischen Mutter- und Kindknoten.
• b) Jeder Knoten hat einen Elternteil, mit Ausnahme der Wurzel.
• c) Jeder Knoten ist mit der Wurzel durch einen eindeutigen Pfad verbunden.
• d) Jeder Knoten ist selbst ein Baum.

Binary Tree (Binärbaum)

Ein Baum, dessen Knoten maximal zwei Kinder haben.

Einfügen von Daten in einen Binärbaum:

• Knoten oder Daten, die kleiner oder gleich der Wurzel sind, gehen an den linken Ast.
• Knoten oder Daten, die größer als die Wurzel sind, gehen an den rechten Zweig.

Traversierung eines Baumes

Das Durchlaufen eines Baumes erfolgt durch das Prüfen jedes Knotens ohne Wiederholung.

Methoden der Traversierung:

• Pre-Order: Wurzel prüfen, linken Zweig in Pre-Order durchlaufen, rechten Zweig in Pre-Order durchlaufen.
• In-Order: Linken Zweig in In-Order durchlaufen, Wurzel untersuchen, rechten Zweig in In-Order durchlaufen.
• Post-Order: Linken Zweig in Post-Order untersuchen, rechten Zweig in Post-Order durchlaufen, Wurzel prüfen.

Beispiel:

    80
   /  \
  60  100
 / \  / \
40 70 90 180

• Pre-Order: 80, 60, 40, 70, 100, 90, 180
• In-Order: 40, 60, 70, 80, 90, 100, 180
• Post-Order: 40, 70, 60, 90, 180, 100, 80

Modul: Insertar_nodo_arbol (dir_ar, nodos)

• Gibt die Adresse des Baumes nach dem Einfügen des Knotens zurück.
• Für den Einfügevorgang wurde folgender Ansatz gewählt:
• Wenn der Knoten kleiner als die Wurzel ist, wird er im linken Zweig festgelegt.
• Wenn er größer ist, wird der rechte Zweig verwendet.
• Die Funktion verwendet Rekursion.

Programmbeispiel: Binärbaum erstellen

#include <arbol.h>
void main() {
    Baum *par = NULL; // Zeiger auf Baum
    par = insertar_nodo_arbol(par, 70);
    par = insertar_nodo_arbol(par, 100);
    par = insertar_nodo_arbol(par, 40);
    par = insertar_nodo_arbol(par, 10);
    printf("Binärbaum erstellt\n\n");
}

Übung: Baum erstellen

Schreiben Sie Anweisungen zum Erstellen des folgenden Baumes:

    100
   /   \
  70   180
 /  \
5   300

void main() {
    Baum *par = NULL;
    int node, i;
    for (i = 0; i <= 10; i++) {
        printf("Geben Sie die Nummer ein:\n\n");
        scanf("%d", &node);
        par = ingresar_nodo_arbol(par, node);
    }
}