Wie funktioniert ein binärer Baum?

Ein binärer Baum ist eine Datenstruktur in Baumform, bei der jeder Knoten höchstens zwei Kindknoten hat: links und rechts.

Funktionsprinzipien:

• Wurzel: Oberster Knoten des Baumes.
• Knoten: Enthalten Daten und Verweise auf Kindknoten.
• Blätter: Knoten ohne Kindknoten.
• Verbindungen: Sind vom Elternknoten zu den Kindknoten gerichtet.

Hauptoperationen:

• Einfügen: Neue Knoten werden an einer bestimmten Stelle im Baum hinzugefügt, wobei die Struktur und Regeln erhalten bleiben (z.B. bei einem binären Suchbaum: kleinere Werte nach links, größere nach rechts).
• Suchen: Durchlaufen der Knoten, um ein bestimmtes Element zu finden. Bei einem binären Suchbaum ist die Suche effizient dank der Datenordnung.
• Löschen: Entfernen eines Knotens mit Umstrukturierung des Baumes.
• Traversieren: Besuch aller Knoten des Baumes in einer bestimmten Reihenfolge:
  • Pre-Order: Wurzel, linker Teilbaum, rechter Teilbaum.
  • Post-Order: linker Teilbaum, rechter Teilbaum, Wurzel.
  • In-Order: linker Teilbaum, Wurzel, rechter Teilbaum (liefert eine sortierte Liste der Elemente bei einem binären Suchbaum).

Vorteile:

• Effiziente Suche, Einfügen und Löschen (bei balancierten Bäumen).
• Wird verwendet, um hierarchische Daten darzustellen.

Beispiel für die Struktur eines Knotens in PHP:

<?php

class Node {
    public $data; // Daten des Knotens
    public $left; // Linker Kindknoten
    public $right; // Rechter Kindknoten

    public function __construct($data) {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}