Detaillierte Erläuterung der Definition und Darstellungsmethode des binären Suchbaums der JavaScript-Datenstruktur

Dieser Artikel stellt hauptsächlich die Definition und Darstellungsmethode des binären Suchbaums der JavaScript-Datenstruktur vor. Er beschreibt kurz das Konzept und die Eigenschaften des binären Suchbaums sowie die Erstellung, Einfügung, Durchquerung und andere Vorgänge des binären Suchbaums Freunde, die sie benötigen, finden Implementierungstipps unter

In diesem Artikel werden die Definition und Darstellungsmethode des binären Suchbaums der JavaScript-Datenstruktur anhand von Beispielen erläutert. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Baum ist eine nichtlineare Datenstruktur, die Daten hierarchisch speichert . Bäume werden zum Speichern von Daten mit hierarchischen Beziehungen verwendet, beispielsweise Dateien in einem Dateisystem. Bäume werden auch zum Speichern geordneter Listen verwendet. Hier wird eine besondere Baumart untersucht: der Binärbaum. Bäume wurden diesen grundlegenden Datenstrukturen vorgezogen, weil die Suche in einem Binärbaum sehr schnell ist (während die Suche in einer verknüpften Liste nicht der Fall ist) und das Hinzufügen oder Entfernen von Elementen zu einem Binärbaum sehr schnell ist (während das Hinzufügen oder Entfernen eines Elements zu einem Array). ist nicht so).

Ein Baum ist eine endliche Menge von n Knoten. Das obere ist die Wurzel und das untere ist der Unterbaum der Wurzel. Ein Baumknoten enthält ein Datenelement und Zweige, die auf seine Unterbäume verweisen. Der Teilbaum, der einem Knoten gehört, wird als Grad des Knotens bezeichnet. Ein Knoten mit Grad 0 wird als Blatt oder Endknoten bezeichnet. Knoten mit einem anderen Grad als 0 werden nichtterminale Knoten oder Verzweigungsknoten genannt. Der Grad des Baumes ist der Maximalwert des Grades jedes Knotens im Baum. Die Hierarchie der Knoten wird ausgehend von der Wurzel definiert, die Ebene 0 ist. Die maximale Knotenebene im Baum wird als Tiefe oder Höhe des Baums bezeichnet.

Binärbaum ist eine besondere Art von Baum mit nicht mehr als zwei untergeordneten Knoten. Binärbäume verfügen über einige spezielle Recheneigenschaften, die einige Operationen an ihnen äußerst effizient machen. Durch die Begrenzung der Anzahl der untergeordneten Knoten auf 2 können effiziente Programme geschrieben werden, um Daten in den Baum einzufügen, zu suchen und zu löschen.

Bevor wir JavaScript zum Erstellen eines Binärbaums verwenden, müssen wir unserem Wörterbuch über Bäume zwei neue Begriffe hinzufügen. Die beiden untergeordneten Knoten eines übergeordneten Knotens werden als linker Knoten bzw. rechter Knoten bezeichnet. In einigen Implementierungen von Binärbäumen enthält der linke Knoten einen bestimmten Wertesatz und der rechte Knoten einen anderen bestimmten Wertesatz. Binärer Suchbaum ist ein spezieller Binärbaum, bei dem relativ kleine Werte im linken Knoten und größere Werte im rechten Knoten gespeichert werden. Diese Funktion macht die Suche sowohl nach numerischen als auch nach nicht numerischen Daten wie Wörtern und Zeichenfolgen sehr effizient.

Der binäre Suchbaum besteht aus Knoten, daher müssen wir ein Knotenobjekt definieren. Der Code lautet wie folgt:

function Node(data,left,right){//结点类
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//显示节点中数据
    return this.data;
}

wo links und right werden jeweils verwendet. Zeigt auf den linken und rechten untergeordneten Knoten.

Als nächstes müssen Sie eine binäre Suchbaumklasse erstellen. Der Code lautet wie folgt:

function BST(){//树类
    this.root=null;
    this.insert=insert;
    this.inOrder=inOrder;
    this.preOrder=preOrder;
    this.postOrder=postOrder;
}

Der nächste Schritt ist der einzufügende Code Knoten. Überqueren Sie die kleinen und fügen Sie sie links ein, die großen rechts. Der Code lautet wie folgt:

function insert(data){//插入操作
    var n=new Node(data,null,null);
    if(this.root==null){//第一个元素
      this.root=n;
    }else{
      var current=this.root;//永远指向根节点
      var parent;
      while(true){//一直运行直到找到左结点或右结点为止
        parent=current;
        if(data<current.data){
          current=current.left;
          if(current==null){//如果没有左节点
            parent.left=n;
            break;
          }
        }else{
          current=current.right;
          if(current==null){//如果没有右节点
            parent.right=n;
            break;
          }//如果有右节点，则跳到while重新执行，将该节点作为parent重新开始判断
        }
      }
    }
}

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Definition und Darstellungsmethode des binären Suchbaums der JavaScript-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!