Implementierung eines binären Suchbaums in JavaScript

Baumdatenstruktur

Ein Baum ist eine Sammlung von Knoten, die durch einige Kanten verbunden sind. Konventionell jeder Knoten des Baums Speichern Sie einige Daten und Verweise auf die untergeordneten Knoten.

Binärer Suchbaum

Ein binärer Suchbaum ist ein binärer Baum, in dem links Knoten mit kleineren Werten und links Knoten mit kleineren Werten gespeichert werden. Höhere Werte werden rechts gespeichert.

Zum Beispiel ist die visuelle Darstellung eines gültigen BST -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

Nun implementieren wir unseren eigenen binären Suchbaum in der JavaScript-Sprache.

Schritt 1: Knotenklasse

Diese Klasse stellt einen einzelnen Knoten dar, der an jedem Punkt im BST vorhanden ist. BST Nichts Vielmehr handelt es sich um eine Sammlung von Knoten, die nach Regeln platzierte Daten und Unterreferenzen speichern. Wie oben erwähnt.

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};

Um eine neue Node-Instanz zu erstellen, können wir diese Klasse mit einigen Daten aufrufen –

const newNode = new Node(23);

Dadurch wird eine neue Node-Instanz erstellt, deren Datensatz auf 23 und die linken und rechten Referenzen auf Null gesetzt sind.

Schritt 2: Klasse „Binärer Suchbaum“:

class BinarySearchTree{
   constructor(){
      this.root = null;
   };
};

Dadurch wird die Klasse „Binärer Suchbaum“ erstellt. Wir können sie mit dem neuen Schlüsselwort aufrufen, um eine zu erstellen Bauminstanz.

Da wir nun die Grundlagen erledigt haben, können wir einen neuen Knoten an der richtigen Stelle einfügen (gemäß den in der Definition beschriebenen BST-Regeln).

Schritt 3: Knoten in BST einfügen

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

Beispiel

Vollständiger binärer Suchbaumcode:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

Das obige ist der detaillierte Inhalt vonImplementierung eines binären Suchbaums in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!