Datenstruktur - Baum

Ein Baum ist eine typische nichtlineare Datenstruktur, die aus Knoten und Kanten, die Knoten verbinden, besteht und dazu verwendet wird, eine hierarchische "Eins-zu-viele"-Beziehung zwischen Elementen darzustellen.


Grundlegende Terminologie der Bäume

Diagramm der Baum-Terminologie
AWurzelknoten
Tiefe 0
BTiefe 1
CTiefe 1
DBlattknoten
Tiefe 2
EBlattknoten
FBlattknoten
WurzelknotenKein Elternknoten, eindeutig
KindknotenDirektes Kind
BlattknotenKeine Kinder
TiefeAnzahl der Kanten von der Wurzel zu diesem Knoten
HöheAnzahl der Kanten von diesem Knoten zum tiefsten Blatt
BinärbaumJeder Knoten hat höchstens 2 Kinder

Um Baumstrukturen zu verstehen, müssen Sie zunächst einige grundlegende Begriffe beherrschen:

BegriffBedeutung
Wurzelknoten (Root)Der Startknoten eines Baums, der keinen Elternknoten hat
Kindknoten (Child)Der Knoten auf der nächsten Ebene, der direkt mit einem gegebenen Knoten verbunden ist
Elternknoten (Parent)Der Knoten auf der vorherigen Ebene, der direkt mit einem gegebenen Knoten verbunden ist
Blattknoten (Leaf)Ein Knoten ohne Kinder, d. h. das Ende eines Baums
Tiefe (Depth)Anzahl der Kanten vom Wurzelknoten zu diesem Knoten; die Wurzel hat die Tiefe 0
Höhe (Height)Anzahl der Kanten von diesem Knoten zum tiefsten Blattknoten

Traversierung eines binären Baums

Vier Traversierungsmethoden für Binärbäume – am Beispiel desselben Baums
1
2
3
4
5

Preorder (Wurzel → links → rechts)

1 2 4 5 3

Inorder (links → Wurzel → rechts)

4 2 5 1 3

Postorder (links → rechts → Wurzel)

4 5 2 3 1

Level-order (Ebene für Ebene)

1 2 3 4 5

Die vier gängigen Traversierungsmethoden sind wie folgt:

TraversierungsmethodeBesuchsreihenfolgeTypische Anwendung
Preorder-TraversierungWurzel → links → rechtsKopieren von Bäumen, Erzeugen von Präfixausdrücken
Inorder-TraversierungLinks → Wurzel → rechtsBST gibt sortierte Sequenz aus
Postorder-TraversierungLinks → rechts → WurzelLöschen von Bäumen, Erzeugen von Postfix-Ausdrücken
Levelorder-TraversierungSchicht für Schicht, von links nach rechtsBFS, Ausgabe nach Schichten

Beispiel

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int value) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* Preorder-Traversierung: Wurzel → links → rechts */
void preOrder(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);   /* Zuerst Wurzel besuchen */
    preOrder(root->left);       /* Dann linken Teilbaum durchlaufen */
    preOrder(root->right);      /* Schließlich rechten Teilbaum durchlaufen */
}

/* Inorder-Traversierung: links → Wurzel → rechts */
void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);        /* Linken Teilbaum zuerst durchlaufen */
    printf("%d ", root->data);   /* Dann die Wurzel besuchen */
    inOrder(root->right);       /* Zuletzt den rechten Teilbaum durchlaufen */
}

/* Postorder-Traversierung: links → rechts → Wurzel */
void postOrder(struct TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);      /* Linken Teilbaum zuerst durchlaufen */
    postOrder(root->right);     /* Dann den rechten Teilbaum durchlaufen */
    printf("%d ", root->data);   /* Zuletzt die Wurzel besuchen */
}

int main() {
    /* Erzeuge den folgenden Binärbaum:
           1
          / \
         2   3
        / \
       4   5   */

    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Preorder: "); preOrder(root);  printf("\n");  /* 1 2 4 5 3 */
    printf("Inorder: "); inOrder(root);   printf("\n");  /* 4 2 5 1 3 */
    printf("Postorder: "); postOrder(root); printf("\n");  /* 4 5 2 3 1 */
    return 0;
}

Binärer Suchbaum (BST)

Binärer Suchbaum (BST) — links kleiner, rechts größer
50
30
70
20
40
60
80

BST-Eigenschaften und Operationen

Eigenschaft: Alle Werte im linken Teilbaum < Wurzel < alle Werte im rechten Teilbaum

Einfügen/Suchen: Bei kleinerem Wert in den linken Teilbaum gehen, bei größerem Wert in den rechten Teilbaum gehen, O(log n) bei balanciertem Baum

Inorder-Traversierung gibt aufsteigende Folge aus: 20 30 40 50 60 70 80

Hinweis: Einfügen in Reihenfolge 1,2,3... degeneriert zu einer verketteten Liste O(n); ein AVL-Baum kann dies lösen

Binärer Suchbaum (BST)Anforderung: Für jeden Knoten sind alle Werte im linken Teilbaum kleiner als der Knoten und alle Werte im rechten Teilbaum größer als der Knoten.

Beispiel

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

/* BST-Einfügen: rekursiv die passende Position basierend auf der Größe des Werts ermitteln
Zeitkomplexität: O(h), h ist die Höhe des Baums, O(log n) bei balanciertem Baum. */

struct TreeNode* insert(struct TreeNode* root, int value) {
    if (root == NULL) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->data = value;
        node->left = node->right = NULL;
        return node;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);   /* Wenn kleiner als Wurzel, in linken Teilbaum einfügen */
    } else if (value > root->data) {
        root->right = insert(root->right, value); /* Wenn größer als root, in den rechten Teilbaum einfügen */
    }
    return root;  /* Wenn gleich, ignorieren (BST speichert normalerweise keine doppelten Werte) */
}

/* BST-Suche: mit aktuellem Knoten vergleichen, um zu entscheiden, ob links oder rechts gesucht wird */
struct TreeNode* search(struct TreeNode* root, int target) {
    if (root == NULL || root->data == target) {
        return root;  /* Ziel gefunden oder Blattknoten erreicht */
    }
    if (target < root->data) {
        return search(root->left, target);   /* Ziel ist kleiner, im linken Teilbaum suchen */
    }
    return search(root->right, target);       /* Ziel ist größer, im rechten Teilbaum suchen */
}

/* In-order-Traversierung (BST-Reihenfolge überprüfen) */
void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

int main() {
    struct TreeNode* root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};

    /* Sequenziell einfügen, um den BST aufzubauen */
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]);
    }

    printf("BST-Inorder-Traversierung (aufsteigend): ");
    inOrder(root);  /* Ausgabe: 20 30 40 50 60 70 80 */
    printf("\n");

    /* Suchtest */
    int target = 40;
    struct TreeNode* found = search(root, target);
    printf("%d %s\n", target, found ? "Gefunden!" : "Nicht gefunden");
    /* Ausgabe: 40 Gefunden! */
    return 0;
}

Im Idealfall (wenn der Baum ausgeglichen bleibt) können BST-Einfügung, -Löschung und -Suche alle O(log n) erreichen. Wenn die Daten jedoch selbst sortiert sind (z. B. Einfügen von 1, 2, 3, 4 ...), degeneriert der BST zu einer verketteten Liste, und die Effizienz sinkt auf O(n). Um dieses Problem zu lösen, hat die Informatik Folgendes entwickelt:AVL-Baumund andere selbstbalancierende binäre Suchbäume.

Weitere Erweiterungen