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
Tiefe 0
Tiefe 2
Um Baumstrukturen zu verstehen, müssen Sie zunächst einige grundlegende Begriffe beherrschen:
| Begriff | Bedeutung |
|---|---|
| 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
Preorder (Wurzel → links → rechts)
1 2 4 5 3Inorder (links → Wurzel → rechts)
4 2 5 1 3Postorder (links → rechts → Wurzel)
4 5 2 3 1Level-order (Ebene für Ebene)
1 2 3 4 5Die vier gängigen Traversierungsmethoden sind wie folgt:
| Traversierungsmethode | Besuchsreihenfolge | Typische Anwendung |
|---|---|---|
| Preorder-Traversierung | Wurzel → links → rechts | Kopieren von Bäumen, Erzeugen von Präfixausdrücken |
| Inorder-Traversierung | Links → Wurzel → rechts | BST gibt sortierte Sequenz aus |
| Postorder-Traversierung | Links → rechts → Wurzel | Löschen von Bäumen, Erzeugen von Postfix-Ausdrücken |
| Levelorder-Traversierung | Schicht für Schicht, von links nach rechts | BFS, Ausgabe nach Schichten |
Beispiel
#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)
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 <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;
}
Weitere ErweiterungenIm 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.