Comment implémenter la traversée de l'arborescence DOM à l'aide de JS

Cette fois, je vais vous montrer comment utiliser JS pour implémenter la traversée de l'arborescence DOM. Quelles sont les précautions pour implémenter la traversée de l'arborescence DOM avec JS Voici un cas pratique, jetons un coup d'œil.

Traversée de l'arbre DOM binaire

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

Traversée de précommande

Visitez le premier 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);
  }
}

modifié 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

Parcourez d'abord le sous-arbre de gauche, puis visitez le nœud racine et enfin parcourez 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

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.

Parcourir des arbres multi-fourches de manière non récursive à l'aide de files d'attente

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

Parcourir la racine nœud d'abord, puis parcourez un chemin jusqu'à la couche la plus profonde et enfin revenez couche par couche.

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 :

Comment utiliser Angular pour implémenter la fonction de demande de données

Gestion des problèmes courants dans la vue- processus d'emballage cli

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!