Implementierung eines binären Suchbaums in JavaScript-js-Tutorial-php.cn

Implementierung eines binären Suchbaums in JavaScript

WBOY

Freigeben： 2023-08-30 09:25:02

nach vorne

411 Leute haben es durchsucht

在 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

Nach dem Login kopieren

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;
   };
};

Nach dem Login kopieren

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

const newNode = new Node(23);

Nach dem Login kopieren

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;
   };
};

Nach dem Login kopieren

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);
         };
      };
   };
};

Nach dem Login kopieren

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);

Nach dem Login kopieren

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!