So implementieren Sie einen Binärbaum in PHP (Codebeispiel)

Binärbaum ist eine grundlegende Datenstruktur in der Informatik. Es handelt sich um die häufigste Baumstruktur, die beispielsweise in der Informatik zum Suchen und Sortieren verwendet wird und in vielen anderen Bereichen der Informatik verwendet wird. PHP ist eine weit verbreitete serverseitige Skriptsprache, die dynamische Webentwicklung unterstützt. In diesem Artikel stellen wir vor, wie man einen Binärbaum mit PHP implementiert.

Was ist ein Binärbaum?

Ein Binärbaum besteht aus mehreren Knoten, jeder Knoten hat höchstens zwei untergeordnete Knoten. Es hat drei Attribute:

• Knotenwert
• Linker Teilbaumzeiger
• Rechter Teilbaumzeiger

Binärbäume sind in die folgenden Kategorien unterteilt:

• Vollständiger Binärbaum: Mit Ausnahme der Blattknoten haben andere Knoten zwei untergeordnete Knoten
• Vollständiger Binärbaum: Wenn die Tiefe des Binärbaums d beträgt, außer der d-ten Ebene, sind alle anderen Ebenen voll, und auf der d-ten Ebene befinden sich alle Blattknoten an aufeinanderfolgenden Positionen auf der linken Seite
• Binärer Suchbaum: Linker Teilbaum Alle Knoten sind kleiner als der Wurzelknotenwert und alle Knotenwerte im rechten Teilbaum sind größer als der Wurzelknotenwert

Um einen Binärbaum zu implementieren

Wir können Klassen verwenden, um die Binärbaumstruktur zu definieren. Jeder Knoten ist ein Objekt mit den folgenden Eigenschaften:

• Wert: Knotenwert
• links: linker Teilbaumzeiger
• rechts: rechter Teilbaumzeiger

Erstellen Sie eine Klasse zur Darstellung des Knotens.

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

Als nächstes müssen wir eine Klasse erstellen, um den Binärbaum darzustellen.

class BinarySearchTree {
    public $root;
    function __construct() {
        $this -> root = null;
    }
}

Als nächstes definieren wir die folgenden Methoden für Binärbäume:

• insert(value): Füge einen Wert in einen Binärbaum ein
• search(value): Finde einen Wert in einem Binärbaum
• delete(value) : Einen Wert aus einem Binärbaum löschen

Knoten einfügen

Die Methode „Knoten einfügen“ fügt den neuen Knoten an der richtigen Stelle ein. Wenn der Baum leer ist, ist der neue Knoten der Wurzelknoten. Andernfalls beginnen wir mit dem Vergleich des Werts des aktuellen Knotens vom Stammknoten aus.

• Wenn der Wert des neuen Knotens kleiner ist als der Wert des aktuellen Knotens, dann fügen wir den neuen Knoten in den linken Teilbaum ein.
• Wenn der Wert des neuen Knotens größer ist als der Wert des aktuellen Knotens, dann fügen wir den neuen Knoten in den rechten Teilbaum ein.
• Wenn der Wert des neuen Knotens gleich dem Wert des aktuellen Knotens ist, ist der Knoten bereits vorhanden und muss nicht eingefügt werden.

Dies ist der Code für die Einfügemethode:

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value < $current -> value) {
                if ($current -> left == null) {
                    $current -> left = $newNode;
                    return;
                } else {
                    $current = $current -> left;
                }
            } else if ($value > $current -> value) {
                if ($current -> right == null) {
                    $current -> right = $newNode;
                    return;
                } else {
                    $current = $current -> right;
                }
            } else {
                return;
            }
        }
    }
}

Find Node

Die Find Node-Methode ist eine einfache rekursive Methode. Vergleichen Sie die Knotenwerte ausgehend vom Wurzelknoten. Wenn die Werte gleich sind, wird der aktuelle Knoten zurückgegeben. Andernfalls, wenn der Wert des Knotens kleiner ist als der gesuchte Wert, fahren Sie mit der Suche im linken Teilbaum fort. Wenn der Wert größer ist als der gesuchte Wert, fahren Sie mit der Suche im richtigen Teilbaum fort.

Dies ist der Code für die Find-Methode:

function search($value) {
    $current = $this -> root;
    while ($current != null) {
        if ($value == $current -> value) {
            return $current;
        } else if ($value < $current -> value) {
            $current = $current -> left;
        } else {
            $current = $current -> right;
        }
    }
    return null;
}

Delete Node

Die Methode „Delete Node“ ist eine der komplexesten Methoden in der gesamten Implementierung. Wie ein Knoten gelöscht wird, hängt von der Anzahl der untergeordneten Knoten des Knotens ab. Folgende Situationen können auftreten:

• Der Knoten ist ein Blattknoten und hat keine untergeordneten Knoten. Löschen Sie den Knoten direkt. Der
• -Knoten hat nur einen untergeordneten Knoten. Ersetzen Sie untergeordnete Knoten durch diesen Knoten. Der
• -Knoten hat zwei untergeordnete Knoten. Suchen Sie den Mindestwert im rechten Teilbaum des Knotens, ersetzen Sie den Mindestwert durch diesen Knoten und entfernen Sie den Mindestwert aus dem rechten Teilbaum.

Dies ist der Code für die Löschmethode:

function delete($value) {
    $current = $this -> root;
    $parent = null;
    while ($current != null) {
        if ($value == $current -> value) {
            if ($current -> left == null && $current -> right == null) {
                if ($parent == null) {
                    $this -> root = null;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = null;
                    } else {
                        $parent -> right = null;
                    }
                }
            } else if ($current -> left == null) {
                if ($parent == null) {
                    $this -> root = $current -> right;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> right;
                    } else {
                        $parent -> right = $current -> right;
                    }
                }
            } else if ($current -> right == null) {
                if ($parent == null) {
                    $this -> root = $current -> left;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> left;
                    } else {
                        $parent -> right = $current -> left;
                    }
                }
            } else {
                $replacementNode = $current -> right;
                while ($replacementNode -> left != null) {
                    $replacementNode = $replacementNode -> left;
                }
                $removeValue = $replacementNode -> value;
                $this -> delete($replacementNode -> value);
                $current -> value = $removeValue;
            }
            return;
        } else if ($value < $current -> value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

Fazit

Jetzt haben wir gelernt, wie man einen Binärbaum in PHP implementiert. Binärbäume sind eine grundlegende Datenstruktur in der Informatik und werden von vielen Algorithmen und Anwendungen genutzt. Wir haben gelernt, wie man Knoten einfügt, Knoten findet und Knoten löscht. Wir können diese Klasse auch erweitern, um andere praktische Methoden zu implementieren.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Binärbaum in PHP (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!