Über die Einrichtung und Durchquerung von Binärbäumen gibt dieser Artikel eine detaillierte Einführung sowie die Algorithmen für die Durchquerung von Binärbäumen vor der Bestellung, die Durchquerung von Binärbäumen in der Reihenfolge und die Durchquerung von Binärbäumen nach der Bestellung Wird auch zitiert, um es für jeden einfacher zu machen, es klarer zu sehen. Die Einleitung dieses Artikels sollte zum leichteren Verständnis mit Binärbäumen und binären Suchbäumen beginnen. Apache PHP MySQL
Knoten: Jedes Element im Baum ein Knoten,
Wurzelknoten: ein Knoten, der sich am Scheitelpunkt des gesamten Baums befindet, er hat keinen übergeordneten Knoten, wie in Abbildung 5 oben gezeigt
untergeordneter Knoten: Nachkommen anderer Knoten
Blätterknoten: Elemente ohne untergeordnete Knoten werden Blattknoten genannt, wie in Abbildung 3 8 24 dargestellt
Binärbaum: Ein Binärbaum ist eine Datenstruktur und seine organisatorische Beziehung ähnelt einem Baum in der Natur . Die Definition in der offiziellen Sprache lautet: Es handelt sich um eine Menge endlicher Elemente, die entweder leer ist oder aus einem Element namens Wurzel und zwei disjunkten Binärbäumen besteht, die als linker Teilbaum bzw. rechter Teilbaum bezeichnet werden.
Binärer Suchbaum:
Der binäre Suchbaum wird auch als binärer Suchbaum (BST) bezeichnet. Er erlaubt uns nur, einen kleineren Wert im linken Knoten als im übergeordneten Knoten und einen kleineren Wert im zu speichern Für größere Werte zeigt das Bild oben einen binären Suchbaum.
Erstellen Sie zunächst eine Klasse zur Darstellung eines binären Suchbaums. Darin sollte sich eine Node-Klasse befinden, um Knoten zu erstellen
function BinarySearchTree () {
var Node = function(key) {
this.key = key,
this.left = null,
this.right = null
}
var root = null
}Sie sollte auch eine Methode haben:
insert(key) Einen neuen Schlüssel einfügen
inOrderTraverse() Durchlaufen des Baums in der richtigen Reihenfolge durchführen und das Ergebnis ausdrucken
preOrderTraverse() führt eine Vorbestellungsdurchquerung des Baums durch und gibt das Ergebnis aus.
postOrderTraverse() führt eine Nachbestellungsdurchquerung des Baums durch und gibt das Ergebnis aus Ergebnis
search(key) sucht nach dem Schlüssel im Baum, gibt true zurück, wenn er existiert, gibt fasle zurück, wenn er nicht existiert
findMin() gibt den minimalen Wert im Baum zurück
findMax() gibt den maximalen Wert im Baum zurück
remove(key) löscht a Geben Sie einen Schlüssel in den Baum ein
Fügen Sie einen neuen Schlüssel in den Baum ein. Die Homepage sollte eine Node-Klasseninstanz erstellen, um den neuen Knoten darzustellen. Sie müssen also die Node-Klasse neu erstellen und übergeben. Der einzufügende Schlüsselwert wird automatisch auf einen neuen Knoten mit null linken und rechten Knoten initialisiert.
Dann müssen zunächst einige Beurteilungen vorgenommen werden , beurteilen Sie, ob der Baum leer ist, wird der neu eingefügte Knoten als Wurzel verwendet. Wenn der Knoten nicht leer ist, rufen Sie eine Hilfsmethode insertNode() auf und übergeben Sie den Wurzelknoten und den neuen Knoten an
this.insert = function(key) {
var newNode = new Node(key)
if(root === null) {
root = newNode
} else {
insertNode(root, newNode)
}
}Definieren Sie die Methode insertNode(). Diese Methode ruft sich selbst rekursiv auf, um den neuen Knoten zu finden.
var insertNode = function(node, newNode) {
if (newNode.key <= node.key) {
if (node.left === null) {
node.left = newNode
}else {
insertNode(node.left, newNode)
}
}else {
if (node.right === null) {
node.right = newNode
}else {
insertNode(node.right, newNode)
}
}
}Um die In-Order-Traversierung zu implementieren, benötigen wir eine inOrderTraverseNode(node)-Methode, die sich selbst rekursiv aufrufen kann, um jeden Knoten zu durchlaufen
this.inOrderTraverse = function() {
inOrderTraverseNode(root)
}Diese Methode gibt den Schlüsselwert jedes Knotens aus. Sie erfordert eine rekursive Beendigungsbedingung - Überprüfen Sie, ob der eingehende Knoten null ist. Rufen Sie sich weiterhin rekursiv auf, um die linke und linke Seite des Knotens zu überprüfen. Der rechte Knoten ist ebenfalls sehr einfach zu implementieren:
var inOrderTraverseNode = function(node) {
if (node !== null) {
inOrderTraverseNode(node.left)
console.log(node.key)
inOrderTraverseNode(node.right)
}
}Der obige Code:
// 实现先序遍历
this.preOrderTraverse = function() {
preOrderTraverseNode(root)
}
var preOrderTraverseNode = function(node) {
if (node !== null) {
console.log(node.key)
preOrderTraverseNode(node.left)
preOrderTraverseNode(node.right)
}
}
// 实现后序遍历
this.postOrderTraverse = function() {
postOrderTraverseNode(root)
}
var postOrderTraverseNode = function(node) {
if (node !== null) {
postOrderTraverseNode(node.left)
postOrderTraverseNode(node.right)
console.log(node.key)
}
} function BinarySearchTree () {
var Node = function(key) {
this.key = key,
this.left = null,
this.right = null
}
var root = null
//插入节点
this.insert = function(key) {
var newNode = new Node(key)
if(root === null) {
root = newNode
} else {
insertNode(root, newNode)
}
}
var insertNode = function(node, newNode) {
if (newNode.key <= node.key) {
if (node.left === null) {
node.left = newNode
}else {
insertNode(node.left, newNode)
}
}else {
if (node.right === null) {
node.right = newNode
}else {
insertNode(node.right, newNode)
}
}
}
//实现中序遍历
this.inOrderTraverse = function() {
inOrderTraverseNode(root)
}
var inOrderTraverseNode = function(node) {
if (node !== null) {
inOrderTraverseNode(node.left)
console.log(node.key)
inOrderTraverseNode(node.right)
}
}
// 实现先序遍历
this.preOrderTraverse = function() {
preOrderTraverseNode(root)
}
var preOrderTraverseNode = function(node) {
if (node !== null) {
console.log(node.key)
preOrderTraverseNode(node.left)
preOrderTraverseNode(node.right)
}
}
// 实现后序遍历
this.postOrderTraverse = function() {
postOrderTraverseNode(root)
}
var postOrderTraverseNode = function(node) {
if (node !== null) {
postOrderTraverseNode(node.left)
postOrderTraverseNode(node.right)
console.log(node.key)
}
}
}var arr = [9,6,3,8,12,15]
var tree = new BinarySearchTree()
arr.map(item => {
tree.insert(item)
})
tree.inOrderTraverse()
tree.preOrderTraverse()
tree.postOrderTraverse()
<p>3<code><br/>3<br/>6<br/>8<br/>9<br/>12<br/>15<br/>6 89<br/>9<br/>6<br/>3<br/>8<br/>12<br/>15<br/>12
<br/>3<br/>8<br/>6<br/>15<br/>12<br/>9<br/>
<p>9</p>6<h2>3</h2>8<p> 12</p>15<p><🎜>Durchlauf nach der Bestellung: <🎜>3<🎜>8<🎜>6<🎜>15<🎜>12<🎜> 9< 🎜><🎜><🎜>Offensichtlich ist das Ergebnis wie erwartet, daher verwenden wir den obigen JavaScript-Code, um das Einfügen von Knoten in den Baum und drei Traversierungsmethoden zu implementieren In einem binären Suchbaum ist der Wert des Knotens ganz links am kleinsten und der Wert des Knotens ganz rechts am größten, sodass der binäre Suchbaum leicht die Maximal- und Minimalwerte ermitteln kann. <🎜><🎜>Finden Sie die Minimalwerte und Maximalwerte<🎜><🎜>Wie geht das? Tatsächlich müssen Sie nur den Wurzelknoten an die Methode minNode/oder maxNode übergeben und dann durch eine Schleife beurteilen, ob der Knoten links (minNode)/rechts (maxNode) null ist <🎜><🎜>Implementierungscode: <🎜> // 查找最小值
this.findMin = function() {
return minNode(root)
}
var minNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 查找最大值
this.findMax = function() {
return maxNode(root)
}
var maxNode = function (node) {
if(node) {
while (node && node.right !== null) {
node =node.right
}
return node.key
}
return null
}this.search = function(key) {
return searchNode(root, key)
}同样，实现它需要定义一个辅助方法,这个方法首先会检验node的合法性，如果为null，直接退出，并返回fasle。如果传入的key比当前传入node的key值小，它会继续递归查找node的左侧节点，反之，查找右侧节点。如果找到相等节点，直接退出，并返回true
var searchNode = function(node, key) {
if (node === null) {
return false
}
if (key < node.key) {
return searchNode(node.left, key)
}else if (key > node.key) {
return searchNode(node.right, key)
}else {
return true
}
}移除节点的实现情况比较复杂，它会有三种不同的情况：
需要移除的节点是一个叶子节点
需要移除的节点包含一个子节点
需要移除的节点包含两个子节点
和实现搜索指定节点一元，要移除某个节点，必须先找到它所在的位置，因此移除方法的实现中部分代码和上面相同：
// 移除节点
this.remove = function(key) {
removeNode(root,key)
}
var removeNode = function(node, key) {
if (node === null) {
return null
}
if (key < node.key) {
node.left = removeNode(node.left, key)
return node
}else if(key > node.key) {
node.right = removeNode(node.right,key)
return node
}else{
//需要移除的节点是一个叶子节点
if (node.left === null && node.right === null) {
node = null
return node
}
//需要移除的节点包含一个子节点
if (node.letf === null) {
node = node.right
return node
}else if (node.right === null) {
node = node.left
return node
}
//需要移除的节点包含两个子节点
var aux = findMinNode(node.right)
node.key = aux.key
node.right = removeNode(node.right, axu.key)
return node
}
}
var findMinNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node
}
return null
}其中，移除包含两个子节点的节点是最复杂的情况，它包含左侧节点和右侧节点，对它进行移除主要需要三个步骤：
需要找到它右侧子树中的最小节点来代替它的位置
将它右侧子树中的最小节点移除
将更新后的节点的引用指向原节点的父节点
有点绕儿，但必须这样，因为删除元素后的二叉搜索树必须保持它的排序性质
tree.remove(8) tree.inOrderTraverse()
打印结果：
3<br/>6<br/>9<br/>12<br/>15<br/>
8 这个节点被成功删除了，但是对二叉查找树进行中序遍历依然是保持排序性质的
到这里，一个简单的二叉查找树就基本上完成了，我们为它实现了，添加、查找、删除以及先中后三种遍历方法
但是实际上这样的二叉查找树是存在一些问题的，当我们不断的添加更大/更小的元素的时候，会出现如下情况：
tree.insert(16) tree.insert(17) tree.insert(18)
来看看现在整颗树的情况：
看图片容易得出它是不平衡的，这又会引出平衡树的概念，要解决这个问题，还需要更复杂的实现，例如：AVL树，红黑树 哎，之后再慢慢去学习吧
相关文章：
Das obige ist der detaillierte Inhalt vonjs_Drei Algorithmen für die Binärbaumdurchquerung in der vorderen, mittleren und hinteren Reihenfolge_Implementierung eines einfachen Binärbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
