Dieser Artikel stellt hauptsächlich den Beispielcode des Javascript-Algorithmus vor. Er hat bestimmte Referenzen und ist für das Erlernen von JavaScript von Nutzen >
Was ist ein Binärbaum?
Ein Binärbaum bedeutet, dass jeder Knoten des Baums höchstens zwei untergeordnete Knoten haben kann.Was ist? ein binärer Suchbaum
Basierend auf dem Binärbaum hat der binäre Suchbaum eine zusätzliche Bedingung, nämlich beim Einfügen eines Werts in den Binärbaum, wenn der eingefügte Wert kleiner als der aktuelle Knoten ist , wird es in den linken Knoten eingefügt, andernfalls wird es in den rechten Knoten eingefügt. Wenn während des Einfügevorgangs der linke Knoten oder der rechte Knoten bereits vorhanden ist, fahren Sie mit dem Vergleich gemäß den oben genannten Regeln fort, bis ein neuer Knoten gefunden wird.Eigenschaften binärer Suchbäume
Aufgrund seiner einzigartigen Datenstruktur hat der binäre Suchbaum eine zeitliche Komplexität von O, unabhängig davon, ob er hinzufügt, löscht oder sucht (. h), h ist die Höhe des Binärbaums. Daher sollte der Binärbaum so kurz wie möglich sein, dh der linke und der rechte Knoten sollten so ausgeglichen wie möglich sein.Konstruktion eines binären Suchbaums
Um einen binären Suchbaum zu erstellen, müssen Sie zunächst die Knotenklasse des Binärbaums erstellen. Aus den Eigenschaften von Binärbäumen ist ersichtlich, dass jede Knotenklasse einen linken Knoten, einen rechten Knoten und den Wert selbst hat. Die Knotenklassen lauten also wie folgt:
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}class Tree{
constructor(param = null) {
if (param) {
this.root = new Node(param);
} else {
this.root = null;
}
}
}Objekts .
Das des binären Suchbaums wurde neu hinzugefügt
Der linke Teilbaum des binären Suchbaums ist kleiner als der Knoten und der rechte Wenn der Teilbaum größer als der Knoten ist, können Sie den Algorithmus zum Hinzufügen eines neuen binären Suchbaums einfach wie folgt schreiben:insert(key) {
if (this.root === null) {
this.root = new Node(key);
} else {
this._insertNode(this.root, key);
}
}
_insertNode(node, key) {
if (key < node.key) {
if (node.left === null) {
node.left = new Node(key);{1}
} else {
this._insertNode(node.left, key);{2}
}
} else if (key > node.key) {
if (node.right === null) {
node.right = new Node(key);{3}
} else {
this._insertNode(node.right, key);{4}
}
}
}Durchquerung des binären Suchbaums
Binäre Suchbäume sind in drei Durchquerungsmethoden unterteilt: Vorbestellung, Mittelbestellung und Nachbestellung.inOrderTraverse(callback) {
this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
if (node) {
this._inOrderTraverse(node.left, callback);
callback(node.key);
this._inOrderTraverse(node.right, callback);
}
}Binäre Suchbaumsuche
Die Suche ist sehr einfach und basiert auf dem Prinzip, dass der linke untergeordnete Knoten kleiner ist als der rechte Der untergeordnete Knoten ist größer als der Knoten Can.search(value) {
if (this.root) {
if (value === this.root.key) {
return true;
} else {
return this._searchNode(value, this.root);
}
}
throw new Error('this.root 不存在');
}
_searchNode(value, node) {
if (!node) {
return false;
}
if (value === node.key) {
return true;
}
if (value > node.key) {
return this._searchNode(value, node.right);
} else if (value < node.key) {
return this._searchNode(value, node.left);
}
}Löschen des binären Suchbaums
Das Löschen ist komplizierter und muss je nach Situation beurteilt werdenremove(key) {
this._removeNode(this.root, key);
}
_removeNode(node, value) {
if (!node) {
return null;
}
if (value > node.key) {
node.right = this._removeNode(node.right, value);
} else if (value < node.key) {
node.left = this._removeNode(node.left, value);
} else {
// 如果没有左子树，那么将右子树根节点作为替换节点
if (!node.left) {
return node.right;
// 如果存在左子树，那么取右子树最小节点作为替换节点
} else if (node.left) {
return this._minNode(node.right);
}
}
}Zusammenfassung
Im Allgemeinen habe ich durch dieses einfache Studium binärer Suchbäume wieder etwas über Rekursion gelernt sind nur einige einfache theoretische Konzepte. Diese tiefgreifende Praxis hat mein Verständnis der Rekursion erheblich vertieft.Erklären Sie die Unterschiede zwischen drei Methoden zur Kapselung der JavaScript-Simulationsimplementierung und ihrer Schreibweise
Erklärung der Require call js-Beispiele in JavaScript
Das obige ist der detaillierte Inhalt vonBeispielcode für den binären Suchbaum des Javascript-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
