Introduction détaillée aux arbres binaires JavaScript (arbres de recherche binaires)

Cet article vous apporte une introduction détaillée aux arbres binaires JavaScript (arbres de recherche binaires). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Il se peut que certaines personnes n'aient pas lu le tas binaire que j'ai écrit dans mon dernier article, j'ai donc copié le concept de base de l'arbre binaire ici si vous l'avez lu. cela, vous pouvez l'ignorer.L'introduction précédente aux concepts de base des arbres binaires De plus, si vous n'êtes pas clair sur la structure des données de la liste chaînée, il est préférable de jeter un œil à la structure de données js que j'ai écrite auparavant - Linked. Liste

Arbre binaire

L'arbre binaire (arbre binaire) est une structure arborescente caractérisée par le fait que chaque nœud a au plus deux nœuds de branche. Un arbre binaire se compose généralement d'un nœud racine, de nœuds de branche, et les nœuds feuilles. Chaque nœud de branche est souvent appelé sous-arbre.

• Nœud racine : le nœud supérieur de l'arbre binaire

• Branche node : En plus du nœud racine et ayant des nœuds feuilles

• nœud feuille : à part lui-même, il n'y a pas d'autres nœuds enfants

Termes courants
Dans un arbre binaire, nous utilisons souvent des nœuds parents et des nœuds enfants pour le décrire. Par exemple, 2 dans l'image est le nœud parent de 6 et 3, et inversement 6 et 3 sont 2 enfants. nœuds.

Trois propriétés des arbres binaires

1. Au i-ième niveau de l'arbre binaire, il y a au plus 2^i-1 nœuds

• Quand i=1, il n'y a qu'un nœud racine, 2^(i-1) = 2^0 = 1

Un arbre binaire de profondeur k a au plus 2^k-1 nœuds

• Quand i=2, 2^k-1 = 2^2 - 1 = 3 nœuds

pour tout arbre Arbre binaire T, si le nombre de points récapitulatifs est n0 et le nombre de nœuds de degré 2 (le nombre de sous-arbres est 2) est n2, alors n0=n2+1

Les trois principaux types d'arbres et d'arbres binaires La différence

• Le nombre de nœuds dans un arbre est d'au moins 1, alors que le nombre de nœuds dans un arbre binaire peut être 0

• Le degré maximum de nœuds dans l'arbre (il n'y a pas de limite au nombre de nœuds), tandis que le degré maximum d'un nœud dans un arbre binaire est 2 🎜>

  Classification des arbres binaires
• Les arbres binaires sont divisés en arbres binaires complets et arbres binaires complets

Arbre binaire complet : un arbre d'une profondeur de Un arbre binaire avec k et 2^k - 1 nœuds est appelé un arbre binaire complet

Arbre binaire complet : Un arbre binaire complet signifie que le côté gauche de la dernière couche est plein, et le côté droit peut être plein ou non. Ensuite, l'arbre binaire dans lequel les niveaux restants sont pleins est appelé un arbre binaire complet (un arbre binaire complet est aussi un arbre binaire complet)

Arbre binaire Arbre de recherche

L'arbre de recherche binaire satisfait les propriétés suivantes :

Si le sous-arbre gauche d'un nœud n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre gauche sont inférieures à la valeur de son nœud racine

Si le sous-arbre gauche ; le sous-arbre droit de n'importe quel nœud n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur de son nœud racine

• Les sous-arbres gauche et droit de n'importe quel nœud ; Le nœud doit également satisfaire la propriété selon laquelle la gauche est petite et la droite est grande

• Donnons un exemple pour comprendre ce qui suit en profondeur
• Un ensemble de données : 12,4,18,1,8,16,20

  Comme le montre la figure ci-dessous, la figure de gauche satisfait les propriétés d'un arbre binaire, et chacun de ses nœuds enfants de gauche est plus petit que le parent nœud, le nœud enfant droit est plus grand que son nœud parent, et les nœuds du sous-arbre gauche sont plus petits que le nœud racine, et les nœuds du sous-arbre droit sont plus grands que le nœud racine

Les principales opérations de l'arbre de recherche binaire :

Rechercher

Insérer

• Traverse (transverse)

• La structure de stockage chaînée de l'arbre de recherche binaire
• A partir de la figure suivante, vous pouvez savoir que les nœuds de l'arbre de recherche binaire contient généralement 4 champs, des éléments de données, des pointeurs pointant respectivement vers ses nœuds gauche et droit et un pointeur pointant vers le nœud parent. Cette structure de stockage est généralement appelée liste chaînée à trois voies.

Utiliser du code pour initialiser le nœud d'un arbre de recherche binaire :

Un pointeur vers le nœud parent parent

un pointeur vers le nœud gauche gauche

• un pointeur vers le nœud droit droit

• a Élément de données, qui peut être une clé et une valeur
Ensuite, nous utilisons du code pour initialiser un arbre de recherche binaire

• • 在二叉搜索树中我们会维护一个root指针，这个就相当于链表中的head指针，在没有任何节点插入的时候它指向空，在有节点插入以后它指向根节点。

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

  创建节点

      static createNode(key, value) {
          return new BinarySearchTree(key, value);
      }

  插入操作

  看下面这张图，13是我们要插入的节点，它插入的具体步骤：

  1. 跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的

  2. 而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置

  3. 而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16

  4. 刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点

  

  通过上面的描述，我们来看看代码是怎么写的

  • 定义两个指针，分别是p和tail，最初都指向root，p是用来指向要插入的位置的父节点的指针，而tail是用来查找插入位置的，所以最后它会指向null，用上图举个例子，p最后指向了6这个节点，而tail最后指向了null（tail为null则说明已经找到了要插入的位置）

  • 循环，tail根据我们上面分析的一步一步往下找位置插入，如果比当前节点小就往左找，大则往右找，一直到tail找到一个空位置也就是null

  • 如果当前的root为null，则说明当前结构中并没有节点，所以插入的第一个节点直接为跟节点，即this.root = node

  • 将插入后的节点的parent指针指向父节点

      insert(node){
          let p = this.root;
          let tail = this.root;
          
          // 循环遍历，去找到对应的位置
          while(tail) {
              p = tail;
              // 要插入的节点key比当前节点小
              if (node.key <h3>查找</h3><p>查找就很简单了，其实和插入差多，都是去别叫左右节点的大小，然后往下找</p>

  • 如果root = null, 则二叉树中没有任何节点，直接return，或者报个错什么的。

  • 循环查找

      search(key) {
          let p = this.root;
          if(!p) {
              return;
          }
          
          while(p && p.key !== key){
              if(p.key<key><h3>遍历</h3>
  <ul class=" list-paddingleft-2">
  <li><p>中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表</p></li>
  <li><p>前序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点</p></li>
  <li><p>后序遍历(postorder)：先左节点，再右节点，最后自己</p></li>
  </ul>
  <p>最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因</p>
  <p>根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为null</p>
  <ul class=" list-paddingleft-2">
  <li><p>先遍历左节点-->yield* this._transverse(node.left)</p></li>
  <li><p>遍历自己 --> yield* node</p></li>
  <li><p>遍历左节点 --> yield* this._transverse(node.right)</p></li>
  </ul>
  <pre class="brush:php;toolbar:false">    transverse() {
          return this._transverse(this.root);
      }
      
      *_transverse(node){
          if(!node){
              return;
          }
          yield* this._transverse(node.left);
          yield node;
          yield* this._transverse(node.right)
      }

  

  看上面这张图，我们简化的来看一下，先访问左节点4，再自己12，然后右节点18，这样输出的就刚好是一个12，4，8

  补充：这个地方用了generater，所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组，这里的前提就当是已经有插入的节点了

     const tree = new BinaryTree();
     //...中间省略插入过程
      
     // 这样就返回了一个有序的数组 
     var arr = [...tree.transverse()].map(item=>item.key);

  完整代码

  class BinaryTreeNode {
    constructor(key, value) {
      // 指向父节点
      this.p = null;
  
      // 左节点
      this.left = null;
  
      // 右节点
      this.right = null;
  
      // 键
      this.key = key;
  
      // 值
      this.value = value;
    }
  }
  
  class BinaryTree {
    constructor() {
      this.root = null;
    }
  
    static createNode(key, value) {
      return new BinaryTreeNode(key, value);
    }
  
    search(key) {
      let p = this.root;
      if (!p) {
        return;
      }
  
      while (p && p.key !== key) {
        if (p.key <h3>总结</h3><p>二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。</p><p class="comments-box-content"></p>

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!