Detaillierte Erläuterung des Binärbaums von JavaScript-Datenstrukturen und -Algorithmen. Grundkenntnisse

Das Konzept des Binärbaums

Binärbaum ist eine endliche Menge von n (n>=0) Knoten. Die Menge ist entweder eine leere Menge (leerer Binärbaum) oder sie besteht aus einem Wurzelknoten und zwei voneinander disjunkten Bäumen bestehend aus dem linken Teilbaum und dem rechten Teilbaum des Wurzelknotens.

Eigenschaften von Binärbäumen

Jeder Knoten hat höchstens zwei Teilbäume, daher gibt es im Binärbaum keinen Knoten mit einem Grad größer als 2. Jeder Knoten im Binärbaum ist ein Objekt, und jeder Datenknoten verfügt über drei Zeiger, nämlich Zeiger auf den übergeordneten Knoten, den linken untergeordneten Knoten und den rechten untergeordneten Knoten. Jeder Knoten ist über Zeiger miteinander verbunden. Die Beziehung zwischen verbundenen Zeigern ist eine Eltern-Kind-Beziehung.

Definition des Binärbaumknotens

Binärbaumknoten sind wie folgt definiert:

Code kopieren Der Code lautet wie folgt:

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

Fünf Grundformen von Binärbäumen

Leerer Binärbaum
Es gibt nur einen Wurzelknoten
Der Wurzelknoten hat nur den linken Teilbaum
Der Wurzelknoten hat nur den rechten Teilbaum
Der Wurzelknoten hat sowohl linke als auch rechte Teilbäume

Für einen gewöhnlichen Baum mit drei Knoten gibt es nur zwei Situationen: zwei Schichten oder drei Schichten. Da der Binärbaum jedoch links und rechts unterscheiden muss, entwickelt er sich zu den folgenden fünf Formen:

Spezieller Binärbaum

Schräger Baum

Wie im 2. und 3. Bild im letzten Bild oben gezeigt.

Vollständiger Binärbaum

Wenn in einem Binärbaum alle Zweigknoten linke und rechte Teilbäume haben und sich alle Blätter auf derselben Ebene befinden, wird ein solcher Binärbaum als vollständiger Binärbaum bezeichnet. Wie unten gezeigt:

Vollständiger Binärbaum

Ein vollständiger Binärbaum bedeutet, dass die linke Seite der letzten Ebene voll ist, die rechte Seite voll sein kann oder nicht und dann die verbleibenden Ebenen voll sind. Ein Binärbaum mit der Tiefe k und der Anzahl der Knoten 2^k - 1 ist ein vollständiger Binärbaum (vollständiger Binärbaum). Es ist ein Baum mit der Tiefe k und ohne Lücken.

Die Merkmale eines vollständigen Binärbaums sind:

Blattknoten können nur auf den unteren beiden Ebenen erscheinen.

Die untersten Blätter müssen auf die linke durchgehende Position konzentriert werden.

Wenn auf der vorletzten Ebene Blattknoten vorhanden sind, müssen diese sich an kontinuierlichen Positionen auf der rechten Seite befinden.

Wenn der Knotengrad 1 ist, hat der Knoten nur noch untergeordnete Elemente.

Ein Binärbaum mit demselben Knotenbaum, ein vollständiger Binärbaum hat die geringste Tiefe.

Hinweis: Ein vollständiger Binärbaum muss ein vollständiger Binärbaum sein, aber ein vollständiger Binärbaum ist nicht unbedingt ein vollständiger Binärbaum.

Der Algorithmus ist wie folgt:

Code kopieren Der Code lautet wie folgt:

bool is_complete(tree *root)
{
Warteschlange q;
Baum *ptr;
// Breitendurchquerung (Ebenendurchquerung) durchführen und NULL-Knoten in die Warteschlange stellen
q.push(root);
While ((ptr = q.pop()) != NULL)
{ 
           q.push(ptr->left);             q.push(ptr->right);  }  

// Bestimmen Sie, ob es unbesuchte Knoten gibt While (!q.is_empty())

{ 
ptr = q.pop();

// Wenn es nicht besuchte Nicht-NULL-Knoten gibt, weist der Baum Lücken auf und ist ein unvollständiger Binärbaum

If (NULL != ptr)

                                                                                             return false;                                                                                                                                           }  

gibt true zurück;
}

Eigenschaften von Binärbäumen

Eigenschaft 1 eines Binärbaums: Es gibt höchstens 2^(i-1) Knoten (i>=1) auf der i-ten Ebene des Binärbaums

Eigenschaft 2 von Binärbäumen: Ein Binärbaum mit Tiefe k hat höchstens 2^k-1 Knoten (k>=1)

Sequentielle Speicherstruktur des Binärbaums

Die sequentielle Speicherstruktur eines Binärbaums verwendet ein eindimensionales Array, um jeden Knoten im Binärbaum zu speichern, und der Speicherort der Knoten kann die logische Beziehung zwischen den Knoten widerspiegeln.

Binär verknüpfte Liste

Da die Anwendbarkeit der sequentiellen Speicherung nicht stark ist, müssen wir die Kettenspeicherstruktur berücksichtigen. Nach internationaler Praxis wird bei der Speicherung von Binärbäumen im Allgemeinen eine Kettenspeicherstruktur verwendet.

Jeder Knoten eines Binärbaums hat höchstens zwei Kinder, daher ist es eine natürliche Idee, ein Datenfeld und zwei Zeigerfelder dafür zu entwerfen. Wir nennen eine solche verknüpfte Liste eine binär verknüpfte Liste.

Binäre Baumdurchquerung

Das Durchlaufen eines Binärbaums bedeutet, vom Wurzelknoten aus zu beginnen und alle Knoten im Binärbaum in einer bestimmten Reihenfolge zu besuchen, sodass jeder Knoten nur einmal besucht wird.

Es gibt drei Möglichkeiten, einen Binärbaum zu durchlaufen:

(1) Vorbestellungsdurchquerung (DLR), besuchen Sie zuerst den Wurzelknoten, durchqueren Sie dann den linken Teilbaum und durchqueren Sie schließlich den rechten Teilbaum. Die Abkürzung root-left-right.

(2) In-Order-Traversal (LDR), durchquert zuerst den linken Teilbaum, besucht dann den Wurzelknoten und durchquert schließlich den rechten Teilbaum. Abgekürzt als left-root-right.

(3) Post-Order-Traversal (LRD), durchquert zuerst den linken Teilbaum, dann den rechten Teilbaum und besucht schließlich den Wurzelknoten. Abgekürzt als Links-Rechts-Wurzel.

Durchquerung vorbestellen:

Wenn der Binärbaum leer ist, wird keine Operation zurückgegeben, andernfalls wird zuerst der Wurzelknoten besucht, dann wird der linke Teilbaum in Vorbestellung durchlaufen und dann wird der rechte Teilbaum in Vorbestellung durchlaufen.

Die Durchlaufreihenfolge ist: A B D H I E J C F K G

Code kopieren Der Code lautet wie folgt:

//Durchquerung vorbestellen
Funktion preOrder(node){
If(!node == null){
          putstr(node.show() " ");
          preOrder(node.left);
          preOrder(node.right);
}
}

Durchlauf in der Reihenfolge:

Wenn der Baum leer ist, wird keine Operation zurückgegeben. Andernfalls durchlaufen Sie ausgehend vom Wurzelknoten (beachten Sie, dass der Wurzelknoten nicht zuerst besucht wird) den linken Teilbaum des Wurzelknotens der Reihe nach und besuchen Sie dann den Wurzelknoten. und schließlich den rechten Teilbaum der Reihe nach durchlaufen.

Die Durchlaufreihenfolge ist: H D I B E J A F K C G

Code kopieren Der Code lautet wie folgt:

//Rekursion verwenden, um die Durchquerung in der Reihenfolge zu implementieren
Funktion inOrder(node){
If(!(node ​​== null)){
inOrder(node.left);//Besuchen Sie zuerst den linken Teilbaum
           putstr(node.show() " ");//Besuchen Sie den Stammknoten erneut
inOrder(node.right);//Letzter Zugriff auf den rechten Teilbaum
}
}

Post-Order-Traversal:

Wenn der Baum leer ist, kehrt die No-Op-Operation zurück, andernfalls werden die linken und rechten Teilbäume von links nach rechts durchlaufen, zuerst die Blätter und dann die Knoten, und schließlich wird der Wurzelknoten besucht.

Die Durchlaufreihenfolge ist: H I D J E B K F G C A

Code kopieren Der Code lautet wie folgt:

//Post-Order-Traversal
Funktion postOrder(node){
If(!node == null){
PostOrder(node.left);
         postOrder(node.right);
           putStr(node.show() " ");
}
}

Binären Suchbaum implementieren

Der binäre Suchbaum (BST) besteht aus Knoten, daher definieren wir ein Knotenknotenobjekt wie folgt:

Code kopieren Der Code lautet wie folgt:

Funktion Node(data,left,right){
This.data = data;
This.left = left;//Speichern Sie den Link zum linken Knoten
This.right = richtig;
This.show = show;
}

Funktion show(){
Return this.data;//Anzeige der im Knoten gespeicherten Daten
}

Finden Sie die Maximal- und Minimalwerte

Das Finden der Minimal- und Maximalwerte auf einem BST ist sehr einfach, da sich der kleinere Wert immer auf dem linken untergeordneten Knoten befindet. Um den Minimalwert auf einem BST zu finden, durchlaufen Sie einfach den linken Teilbaum, bis der letzte Knoten gefunden wird

Finden Sie den Mindestwert

Code kopieren Der Code lautet wie folgt:

Funktion getMin(){
var current = this.root;
While(!(current.left == null)){
Current = current.left;
}
Gibt current.data zurück;
}

Diese Methode durchläuft nacheinander den linken Teilbaum des BST, bis sie zum Knoten ganz links des BST gelangt, der wie folgt definiert ist:

Code kopieren Der Code lautet wie folgt:

current.left = null;

Zu diesem Zeitpunkt ist der auf dem aktuellen Knoten gespeicherte Wert der Mindestwert

Finden Sie den Maximalwert

Um den Maximalwert auf BST zu finden, muss nur der rechte Teilbaum durchlaufen werden, bis der letzte Knoten gefunden wird, und der auf diesem Knoten gespeicherte Wert ist der Maximalwert.

Code kopieren Der Code lautet wie folgt:

Funktion getMax(){
var current = this.root;
While(!(current.right == null)){
            current = current.right;
}
Gibt current.data zurück;
}