Résumé des méthodes de traversée de l'arborescence DOM de l'opération JS

Cette fois, je vais vous apporter un résumé des méthodes de traversée de l'arborescence DOM de l'opération JS. Quelles sont les précautions pour la traversée de l'arborescence DOM de l'opération JS. Voici des cas pratiques, jetons un coup d'œil.

L'exemple de cet article décrit la méthode de traversée de l'arborescence DOM implémentée par JavaScript. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Parcours de l'arbre DOM binaire

function Tree() {
   var Node = function(key){
      this.key = key;
      this.left = null;
      this.right = null;
   }
   root =null;
}

Précommande traversée

Visitez d'abord le nœud racine, puis parcourez le sous-arbre de gauche et enfin parcourez le sous-arbre de droite

Tree.prototype.preOrderTraverse = function(callback){
  preOrder(root, callback);
}
var preOrder = function(node,callback){
  if(node !== null){
    callback(node.key);
    preOrder(node.left, callback);
    preOrder(node.right, callback);
  }
}

Modifiez en arbre binaire DOM :

var preOrder = function(node,callback) {
  callback(node);
  if(node.firstElementChild) {//先判断子元素节点是否存在
     this.preOrder(node.firstElementChild,callback);
  }
  if(node.lastElementChild) {
    this.preOrder(node.lastElementChild,callback);
  }
};

Parcours dans l'ordre

Parcourt d'abord le sous-arbre de gauche, puis visite le nœud racine et traverse enfin le sous-arbre de droite.

Tree.prototype.inOrderTraverse = function(callback){
  inOrder(root, callback);
}
var inOrder = function(node,callback){
  if(node !== null){
    inOrder(node.left,callback);
    callback(node.key);
    inOrder(node.right, calback);
  }
}

Modifier vers l'arbre binaire DOM :

var inOrder = function(node,callback){
  if(node.firstElementChild) {
  this.inOrder(node.firstElementChild);
  }
  callback(node);
  if(node.lastElementChild) {
  this.inOrder(node.lastElementChild);
  }
}

Parcours post-ordre

Parcourez d'abord le sous-arbre de gauche, puis celui de droite Sous-arbre, Visitez enfin le nœud racine.

Tree.prototype.postOrderTraverse = function(callback){
  postOrder(root, callback);
}
var postOrder = function(node,callback){
  if(node !== null){
    postOrder(node.left,callback);
    postOrder(node.right, calback);
    callback(node.key);
  }
}

Modifier vers l'arbre binaire DOM :

var postOrder = function(node,callback){
  if(node.firstElementChild) {
  this.postOrder(node.firstElementChild);
  }
  if(node.lastElementChild) {
  this.postOrder(node.lastElementChild);
  }
  callback(node);
}

Parcours de l'arbre DOM multi-fork

Traversée en largeur d'abord

traverse d'abord le nœud racine, puis visite les nœuds de premier niveau, les nœuds de deuxième niveau, ...., jusqu'à ce que l'on accède au dernier niveau.

À l'aide de files d'attente, parcourez des arbres à plusieurs fourches de manière non récursive

Tree.prototype.BFSearch = function(node,callback){
  var queue=[];
  while(node!=null){
      callback(node);
    if(node.children.length!=0){
    for (var i=0;i<node.children.length;i++){
      queue.push(node.children[i]);//借助于队列,暂存当前节点的所有子节点
    }
    }
      node=queue.shift();//先入先出，借助于数据结构：队列
  }
};

Parcours en profondeur d'abord

Traversez d'abord le nœud racine, puis parcourez un chemin jusqu'au niveau le plus profond, et enfin revenez niveau par niveau.

Avec l'aide de la pile, une traversée en profondeur d'abord des arbres DOM multi-fork est réalisée.

Tree.prototype.DFSearch = function(node,callback){
    var stack=[];
    while(node!=null){
    callback(node);
    if(node.children.length!=0){
    for (var i=node.children.length-1;i>=0;i--){//按照相反的子节点顺序压入栈
      stack.push(node.children[i]);//将该节点的所有子节点压入栈
    }
    }
      node = stack.pop();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)
  }
};

Les parcours en pré-ordre, dans l'ordre et après-ordre de l'arbre DOM binaire sont des cas particuliers de parcours en profondeur d'abord

Par conséquent, reportez-vous au parcours en profondeur d'abord, avec l'aide de La pile peut implémenter le parcours en pré-ordre, dans l'ordre et après-ordre de l'arbre DOM binaire de manière non récursive

Implémenter de manière non récursive le parcours en pré-ordre de l'arbre DOM binaire

Tree.prototype.preOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        callback.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      node=node.lastElementChild;
    }
  };

Implémente de manière non récursive le parcours dans l'ordre d'un arbre DOM binaire

Tree.prototype.inOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      callback(node);
      node=node.lastElementChild;
    }
  };

Implémente de manière non récursive le parcours post-ordre d'un arbre DOM binaire

① Chaque nœud est poussé deux fois sur la pile
② Dans le corps de la boucle, chaque fois qu'un nœud est sauté ; up et assigné au nœud
③ Si le nœud est toujours égal au nœud principal de la pile, cela signifie que le nœud Ses enfants n'ont pas encore été exploités, et ses enfants doivent être ajoutés à la pile
④ Sinon, cela signifie que le nœud apparaît pour la deuxième fois et que le nœud est accédé.

En d'autres termes, la première fois qu'il apparaît, poussez l'enfant du nœud sur la pile, et la deuxième fois qu'il apparaît, accédez au nœud

TreeWalker.prototype.postOrder = function(node,callback) {//非递归实现
  var stack=[];
    stack.push(node);
    stack.push(node);
  while(stack.length != 0)
  {
    node = stack.pop();
    if(stack.length != 0 && node==stack[stack.length-1])
    {
      if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);
      if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);
    }
    else
        callback(node);
  }
}

Je crois que vous maîtrisez la méthode après avoir lu le cas dans cet article , pour un contenu plus passionnant, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Explication détaillée des cas d'utilisation de la fonction de rappel JS

PHP implémente rapidement la méthode de déduplication de tableau

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!