Définition et exemples d'utilisation de l'arbre de recherche binaire JavaScript

Cet article présente principalement la méthode de définition et de représentation de l'arbre de recherche binaire de la structure de données JavaScript. Il décrit brièvement le concept et les caractéristiques de l'arbre de recherche binaire et la création, l'insertion, le parcours et d'autres opérations de l'arbre de recherche binaire dans JavaScript. Pour des conseils d'implémentation, les amis qui en ont besoin peuvent se référer à

Cet article explique la méthode de définition et de représentation de l'arbre de recherche binaire de la structure de données JavaScript à travers des exemples. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

L'arbre est une structure de données non linéaire qui stocke les données de manière hiérarchique . Les arbres sont utilisés pour stocker des données avec des relations hiérarchiques, comme les fichiers dans un système de fichiers ; les arbres sont également utilisés pour stocker des listes ordonnées. Un type particulier d’arbre sera étudié ici : l’arbre binaire. Les arbres ont été choisis plutôt que ces structures de données de base car la recherche sur un arbre binaire est très rapide (contrairement à la recherche sur une liste chaînée), et l'ajout ou la suppression d'éléments d'un arbre binaire est également très rapide (lors de l'ajout ou de la suppression d'un élément d'un le tableau n'est pas) donc).

Un arbre est un ensemble fini de n nœuds. Celui du haut est la racine, et celui du bas est le sous-arbre de la racine. Un nœud d'arbre contient un élément de données et plusieurs branches pointant vers ses sous-arbres. Le sous-arbre appartenant à un nœud est appelé le degré du nœud . Un nœud de degré 0 est appelé une feuille ou un nœud terminal. Les nœuds avec un degré autre que 0 sont appelés nœuds non terminaux ou nœuds de branche . Le degré de l'arbre est la valeur maximale du degré de chaque nœud de l'arbre. La hiérarchie des nœuds est définie à partir de la racine, qui est le niveau 0. Le niveau maximum de nœuds dans l'arbre est appelé la profondeur ou la hauteur de l'arbre.

L'arbre binaire est un type spécial d'arbre avec pas plus de deux nœuds enfants. Les arbres binaires ont des propriétés de calcul spéciales qui rendent certaines opérations extrêmement efficaces. En limitant le nombre de nœuds enfants à 2, des programmes efficaces peuvent être écrits pour insérer, rechercher et supprimer des données dans l'arborescence.

Avant d'utiliser JavaScript pour créer un arbre binaire, nous devons ajouter deux nouveaux termes à notre dictionnaire sur les arbres. Les deux nœuds enfants d’un nœud parent sont appelés respectivement nœud gauche et nœud droit. Dans certaines implémentations d'arbres binaires, le nœud de gauche contient un ensemble spécifique de valeurs et le nœud de droite contient un autre ensemble spécifique de valeurs. Arbre de recherche binaire est un arbre binaire spécial dans lequel des valeurs relativement petites sont stockées dans le nœud de gauche et des valeurs plus grandes sont stockées dans le nœud de droite. Cette fonctionnalité rend les recherches très efficaces, tant pour les données numériques que non numériques, telles que les mots et les chaînes.

L'arbre de recherche binaire est composé de nœuds, nous devons donc définir un objet Node, le code est le suivant :

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

où gauche et right sont utilisés respectivement Points vers les nœuds enfants gauche et droit.

Ensuite, vous devez créer une classe d'arbre de recherche binaire. Le code est le suivant :

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

Le prochain est le code pour insérer des nœuds. . Parcourez les petits et insérez-les à gauche, et les grands à droite. Le code est le suivant :

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重新开始判断
        }
      }
    }
}

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!