Binärbaum

Zuletzt aktualisiert 1. Juli 2026

Ein Binärbaum ist eine Hierarchie, in der jeder Knoten höchstens zwei Kinder hat, das linke und das rechte Kind. Der oberste Knoten ist die Wurzel, Knoten ohne Kinder sind Blätter, und die Anzahl der Kanten von der Wurzel bis zum tiefsten Blatt ist die Höhe des Baums. Anders als ein binärer Suchbaum hat ein einfacher Binärbaum keine Ordnungsregel – es geht nur um die Form. Drücke oben auf Play, um zu sehen, wie sich ein Baum Ebene für Ebene füllt und dann in-order (links, Knoten, rechts) durchlaufen wird.

Binärbäume bilden die Grundlage vieler Strukturen – binäre Suchbäume, Heaps, Ausdrucksbäume und mehr. Traversierungen besuchen jeden Knoten in einer definierten Reihenfolge: In-Order, Pre-Order und Post-Order sind die drei Tiefensuch-Durchläufe, jeder nützlich für andere Aufgaben.

Terminologie

Begriff	Bedeutung
Wurzel	Der oberste Knoten, ohne Elternknoten
Blatt	Ein Knoten ohne Kinder
Höhe	Längster Wurzel-zu-Blatt-Pfad (in Kanten)
Tiefe	Abstand eines Knotens von der Wurzel
Vollständig	Alle Ebenen voll bis auf ggf. die letzte, die von links nach rechts gefüllt wird

Die drei Tiefensuch-Traversierungen

Traversierung	Reihenfolge	Typische Verwendung
In-Order	Links, Knoten, rechts	Sortierte Ausgabe eines BST
Pre-Order	Knoten, links, rechts	Baum kopieren / serialisieren
Post-Order	Links, rechts, Knoten	Baum löschen / auswerten

Durchgerechnetes Beispiel

In-Order-Traversierung des aus [4, 2, 6, 1, 3, 5] (Ebene für Ebene gefüllten) Baums:

Schritt	Am Knoten	Aktion
1	`4`	Rekursion in den linken Teilbaum von `4`, bevor er besucht wird
2	`2`	Rekursion in den linken Teilbaum von `2`, bevor er besucht wird
3	`1`	Blatt, kein linkes Kind: besuche `1`, Ausgabe `[1]`
4	`2`	Links fertig: besuche `2`, Ausgabe `[1, 2]`, dann Rekursion nach rechts
5	`3`	Blatt: besuche `3`, Ausgabe `[1, 2, 3]`
6	`4`	Linker Teilbaum fertig: besuche `4`, Ausgabe `[1, 2, 3, 4]`, dann Rekursion nach rechts
7	`5`	Linkes Kind von `6`, ein Blatt: besuche `5`, Ausgabe `[1, 2, 3, 4, 5]`
8	`6`	Links fertig, kein rechtes Kind: besuche `6`, Ausgabe `[1, 2, 3, 4, 5, 6]`

Wann man einen Binärbaum verwendet

Verwenden, wenn	Vermeiden, wenn
Du inhärent hierarchische Daten modellieren musst (Dateisysteme, Ausdrucksbäume, DOM)	Die Daten flach sind und eine Liste oder ein Array genügen würde – ein Baum bringt nur Overhead
Du geordnete Operationen willst und ihn ausbalanciert halten kannst (ein BST oder selbstbalancierender Baum)	Du eine Schlüsselsuche im Durchschnitt in `O(1)` brauchst – eine Hash-Tabelle schlägt jeden Baum
Du strukturierte Daten in In-Order, Pre-Order oder Post-Order verarbeiten musst	Knoten in sortierter Reihenfolge in einen unbalancierten BST eingefügt werden – er degeneriert zu einer `O(n)`-Liste
Bereichsabfragen oder geordnete Iteration wichtig sind, was Hash-Tabellen nicht bieten	Der Speicher knapp ist – jeder Knoten trägt zwei Kindzeiger zusätzlich zur Nutzlast

Binary Tree-Code

Eine saubere, lauffähige Binary Tree-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.

Binary Tree-Code in PythonPython
1from collections import deque2
3
4class Node:5    def __init__(self, value):6        self.value = value7        self.left = None8        self.right = None9
10
11def insert(root, value):12    # Level-order insert: fill the first empty child slot found13    if root is None:14        return Node(value)15    queue = deque([root])16    while queue:17        node = queue.popleft()18        if node.left is None:19            node.left = Node(value)20            return root21        queue.append(node.left)22        if node.right is None:23            node.right = Node(value)24            return root25        queue.append(node.right)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36    root = insert(root, value)37
38print("Root:   ", root.value)39print("Inorder:", inorder(root))
Führe diesen Code im Python-Playground aus

Binary Tree-Code in JavaScriptJavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.left = null;5        this.right = null;6    }7}8
9class BinaryTree {10    constructor() {11        this.root = null;12    }13
14    // Insert at the first free spot, top to bottom (level order)15    insert(value) {16        const node = new Node(value);17        if (!this.root) {18            this.root = node;19            return;20        }21        const queue = [this.root];22        while (queue.length > 0) {23            const current = queue.shift();24            if (!current.left) {25                current.left = node;26                return;27            }28            if (!current.right) {29                current.right = node;30                return;31            }32            queue.push(current.left, current.right);33        }34    }35
36    inorder(node = this.root, out = []) {37        if (!node) return out;38        this.inorder(node.left, out);39        out.push(node.value);40        this.inorder(node.right, out);41        return out;42    }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));
Führe diesen Code im JavaScript-Playground aus

Binary Tree-Code in JavaJava
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5    static class Node {6        int value;7        Node left, right;8        Node(int value) { this.value = value; }9    }10
11    static Node root;12
13    // Insert at the first free slot in level order (keeps the tree complete)14    static void insert(int value) {15        Node node = new Node(value);16        if (root == null) { root = node; return; }17        Queue<Node> queue = new ArrayDeque<>();18        queue.add(root);19        while (!queue.isEmpty()) {20            Node cur = queue.poll();21            if (cur.left == null) { cur.left = node; return; }22            if (cur.right == null) { cur.right = node; return; }23            queue.add(cur.left);24            queue.add(cur.right);25        }26    }27
28    // Inorder: left subtree, node, right subtree29    static void inorder(Node node, StringBuilder sb) {30        if (node == null) return;31        inorder(node.left, sb);32        sb.append(node.value).append(" ");33        inorder(node.right, sb);34    }35
36    public static void main(String[] args) {37        for (int v = 1; v <= 7; v++) insert(v);38        StringBuilder sb = new StringBuilder();39        inorder(root, sb);40        System.out.println("Root: " + root.value);41        System.out.println("Inorder: " + sb.toString().trim());42    }43}
Führe diesen Code im Java-Playground aus

Binary Tree-Code in C++C++
1#include <iostream>2
3struct Node {4    int value;5    Node* left = nullptr;6    Node* right = nullptr;7    explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11    if (root == nullptr) return new Node(value);12    if (value < root->value) root->left = insert(root->left, value);13    else root->right = insert(root->right, value);14    return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19    if (node == nullptr) return;20    inorder(node->left);21    std::cout << node->value << " ";22    inorder(node->right);23}24
25int countNodes(const Node* node) {26    if (node == nullptr) return 0;27    return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31    Node* root = nullptr;32    for (int value : {8, 3, 10, 1, 6, 14, 4}) {33        root = insert(root, value);34    }35    std::cout << "In-order: ";36    inorder(root);37    std::cout << "\n";38    std::cout << "Node count: " << countNodes(root) << "\n";39    return 0;40}
Führe diesen Code im C++-Playground aus

Binary Tree-Code in CC
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* left;7    struct Node* right;8} Node;9
10Node* newNode(int value) {11    Node* n = malloc(sizeof(Node));12    n->value = value;13    n->left = n->right = NULL;14    return n;15}16
17Node* insert(Node* root, int value) {18    if (root == NULL) return newNode(value);19    if (value < root->value) root->left = insert(root->left, value);20    else root->right = insert(root->right, value);21    return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26    if (node == NULL) return;27    inorder(node->left);28    printf("%d ", node->value);29    inorder(node->right);30}31
32int countNodes(const Node* node) {33    if (node == NULL) return 0;34    return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38    int values[] = {8, 3, 10, 1, 6, 14, 4};39    Node* root = NULL;40    for (int i = 0; i < 7; i++) root = insert(root, values[i]);41    printf("In-order: ");42    inorder(root);43    printf("\n");44    printf("Node count: %d\n", countNodes(root));45    return 0;46}
Führe diesen Code im C-Playground aus

Binärbaum-FAQ

Was ist der Unterschied zwischen einem Binärbaum und einem binären Suchbaum?

Ein Binärbaum beschränkt jeden Knoten lediglich auf höchstens zwei Kinder, ohne jede Ordnung. Ein binärer Suchbaum fügt die Regel hinzu, dass alles im linken Teilbaum kleiner und alles im rechten Teilbaum größer ist, was das Suchen schnell macht.

Was ist eine In-Order-Traversierung?

Die In-Order-Traversierung besucht rekursiv zuerst den linken Teilbaum, dann den Knoten und dann den rechten Teilbaum. Für einen binären Suchbaum ergibt das die Werte in aufsteigend sortierter Reihenfolge, weshalb sie die am häufigsten gezeigte Traversierung ist.

Was ist ein vollständiger Binärbaum?

Ein vollständiger Binärbaum hat alle Ebenen vollständig gefüllt bis auf ggf. die letzte, die von links nach rechts gefüllt wird. Diese Form erlaubt es, den Baum kompakt in einem Array zu speichern (ohne Kindzeiger), so wie binäre Heaps implementiert werden.

Wann sollte ich einen Binärbaum statt eines Arrays oder einer Hash-Tabelle verwenden?

Greife zu einem Baum, wenn deine Daten von Natur aus hierarchisch sind oder wenn du geordnete Operationen wie Bereichsabfragen und sortierte Iteration brauchst, was Hash-Tabellen nicht bieten. Wenn du nur schnelle Schlüsselsuche ohne Ordnung brauchst, schlägt der durchschnittliche O(1)-Zugriff einer Hash-Tabelle einen Baum, und für flache Daten ist ein Array einfacher und cache-freundlicher.

Was ist der Unterschied zwischen der Höhe und der Tiefe eines Binärbaums?

Die Tiefe wird von der Wurzel nach unten bis zu einem bestimmten Knoten gemessen: die Anzahl der Kanten auf dem Pfad von der Wurzel zu diesem Knoten. Die Höhe wird von einem Knoten nach unten bis zu seinem tiefsten Blatt gemessen, sodass die Höhe des gesamten Baums die Tiefe seines tiefsten Knotens ist. Ein Baum mit einem einzigen Knoten hat die Höhe 0, und sein einziger Knoten hat ebenfalls die Tiefe 0.

Warum ist ein unbalancierter Binärbaum so leistungsschwach?

Suchen, Einfügen und Löschen in einem binären Suchbaum kosten O(h), wobei h die Höhe ist. Werden Schlüssel in sortierter Reihenfolge eingefügt, wird der Baum zu einer geraden Linie, sodass h bis auf n wächst und jede Operation zu O(n) degeneriert – nicht besser als eine verkettete Liste. Selbstbalancierende Bäume wie AVL- oder Rot-Schwarz-Bäume halten die Höhe bei O(log n), um das zu verhindern.