Heim  >  Artikel  >  Web-Frontend  >  Welche Methoden gibt es für JS, um die DOM-Baumdurchquerung zu implementieren?

Welche Methoden gibt es für JS, um die DOM-Baumdurchquerung zu implementieren?

php中世界最好的语言
php中世界最好的语言Original
2018-05-31 10:20:421486Durchsuche

Dieses Mal werde ich Ihnen vorstellen, welche Methoden zum Durchlaufen des DOM-Baums mit JS verwendet werden können und welche Vorsichtsmaßnahmen für die Implementierung des Durchlaufens des DOM-Baums mit JS gelten. Das Folgende ist ein praktischer Fall , lass uns einen Blick darauf werfen.

Binäre DOM-Baumdurchquerung

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

Vorbestellungsdurchquerung

Besuchen Sie zuerst den Wurzelknotenpunkt. Durchqueren Sie dann den linken Teilbaum und schließlich den rechten Teilbaum.

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

wurde in einen DOM-Binärbaum geändert:

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

In-Reihenfolge-Durchquerung

Zuerst Durchqueren Sie den linken Teilbaum, besuchen Sie dann den Wurzelknoten und durchqueren Sie schließlich den rechten Teilbaum.

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

wird in einen DOM-Binärbaum geändert:

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

Post-Order-Traversal

Durchläuft zuerst den linken Teilbaum und dann den rechten Teilbaum. und besucht schließlich den Wurzelknotenpunkt.

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

geändert in DOM-Binärbaum:

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

Durchquerung des Multi-Fork-DOM-Baums

Breite- erste Durchquerung

Durchqueren Sie zuerst den Wurzelknoten und besuchen Sie dann den Knoten der ersten Ebene, den Knoten der zweiten Ebene usw., bis auf die letzte Ebene zugegriffen wird.

Multi-Fork-Bäume nicht rekursiv mit Hilfe von Warteschlangen durchqueren

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();//先入先出,借助于数据结构:队列
  }
};

Depth-First-Traversal

Traqueren Sie zuerst den Wurzelknoten , und dann entlang der Traverse einen Pfad zur tiefsten Schicht und schließlich Schicht für Schicht zurück.

Mit Hilfe des Stapels wird die Tiefendurchquerung von DOM-Bäumen mit mehreren Gabeln realisiert.

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();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)
  }
};

Die Durchquerung des binären DOM-Baums vor, in der Reihenfolge und nach der Reihenfolge ist ein Sonderfall der Tiefendurchquerung

Beziehen Sie sich daher auf Tiefendurchquerung, mit Hilfe des Stapels, Sie können die Durchquerung binärer DOM-Bäume vor, in der Reihenfolge und nach der Reihenfolge auf nicht rekursive Weise implementieren

Nicht rekursive Implementierung der Vorbestellungsdurchquerung binärer DOM-Bäume

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

Nicht rekursive Implementierung der In-Order-Durchquerung eines binären DOM-Baums

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

Nein -rekursive Implementierung der Post-Order-Traversierung eines binären DOM-Baums

① Jeder Knoten wird zweimal auf den Stapel geschoben
② Im Schleifenkörper wird jedes Mal ein Knoten angezeigt und zugewiesen zum Knoten
③ Wenn der Knoten immer noch gleich dem Kopfknoten des Stapels ist, bedeutet dies, dass die untergeordneten Knoten des Knotens noch nicht vorhanden sind. Nach der Operation sollten seine untergeordneten Elemente dem Stapel hinzugefügt werden
④ Andernfalls bedeutet dies Folgendes Der Knoten wird zum zweiten Mal herausgesprungen und auf den Knoten zugegriffen.

Mit anderen Worten, wenn es zum ersten Mal erscheint, schieben Sie das Kind des Knotens auf den Stapel, und wenn es zum zweiten Mal auftaucht, greifen Sie auf den Knoten zu

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

Ich glaube, Sie haben die Methode danach gemeistert Lesen Sie den Fall in diesem Artikel und vieles mehr. Wie aufregend, achten Sie bitte auf andere verwandte Artikel auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Wie man Angular bedient, um Datenanforderungen zu implementieren

Wie man einen Knoten betreibt und asynchron zur Steuerung verwendet Parallelität

Das obige ist der detaillierte Inhalt vonWelche Methoden gibt es für JS, um die DOM-Baumdurchquerung zu implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn