Implémentation d'un arbre de recherche binaire en JavaScript

Structure de données d'arbre

Un arbre est une collection de nœuds reliés par des arêtes. Par convention, chaque nœud de l'arbre Enregistrez certaines données et références à ses nœuds enfants.

Arbre de recherche binaire

Un arbre de recherche binaire est un arbre binaire dans lequel les nœuds avec des valeurs plus petites sont stockés à gauche et les nœuds avec des valeurs plus petites sont stockés à gauche. Les valeurs plus élevées sont stockées à droite.

Par exemple, la représentation visuelle d'un BST valide est -

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

Implémentons maintenant notre propre arbre de recherche binaire en langage JavaScript.

Étape 1 : Classe de nœud

Cette classe représentera un seul nœud présent à chaque point du BST. BST Rien Il s'agit plutôt d'un ensemble de nœuds qui stockent des données et des sous-références placées selon des règles. Comme mentionné ci-dessus.

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

Pour créer une nouvelle instance de Node, nous pouvons appeler cette classe avec des données -

const newNode = new Node(23);

Cela créera une nouvelle instance de Node avec ses données définies sur 23 et les références gauche et droite à null.

Étape 2 : Classe d'arbre de recherche binaire :

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

Cela créera la classe d'arbre de recherche binaire, nous pouvons l'appeler en utilisant le nouveau mot-clé pour créer un instance d'arbre.

Maintenant que nous avons fait les bases, allons-y et insérons un nouveau nœud au bon emplacement (selon les règles BST décrites dans la définition).

Étape 3 : Insérer un nœud dans BST

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

Exemple

Code d'arbre de recherche binaire complet :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!