JSを使用してDOMツリートラバーサルを実装する方法

今回は、JS を使用して DOM ツリー トラバーサルを実装する方法を説明します。JS を使用して DOM ツリー トラバーサルを実装する場合の 注意事項 について説明します。

バイナリDOMツリー走査

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

事前順序走査

最初にルートノードにアクセスし、次に左側のサブツリーを走査し、最後に右のサブツリーを走査します

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

DOMバイナリツリーに変更します:

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

順番トラバーサル

最初に左側のサブツリーをトラバースし、次にルート ノードにアクセスし、最後に右側のサブツリーをトラバースします。

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

DOM バイナリ ツリーに変更:

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

事後トラバーサル

最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルート ノードにアクセスします。

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

DOM バイナリ ツリーに変更:

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

マルチフォーク DOM ツリーのトラバーサル

幅優先トラバーサル

最初にルート ノードをトラバースし、次に第 1 レベルのノードにアクセスし、次に第 2 レベルのノードにアクセスします。レベル ノード...、最後の層にアクセスするまで。

キューを使用して非再帰的な方法でマルチフォーク ツリーをトラバースします

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

深さ優先トラバーサル

最初にルート ノードをトラバースし、次にパスに沿って最も深いレベルまでトラバースし、最後にレイヤーを返しますレイヤーごとに。

スタックを使用して、マルチフォーク DOM ツリーの深さ優先の走査を実現します。

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

バイナリ DOM ツリーの前順序、中間順序、後順序のトラバーサルは、深さ優先トラバーサルの特殊なケースです

したがって、深さ優先トラバーサルを参照し、スタックの助けを借りて、バイナリ DOM ツリーは非再帰的な方法で実装できます 事前順序、順序内および事後探索

バイナリ DOM ツリーの事前順序トラバーサルの非再帰実装

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

非再帰実装バイナリ DOM ツリーの順序トラバーサルの例

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

バイナリ DOM ツリーの非再帰実装 DOM ツリーの事後トラバース

① 各ノードはスタックに 2 回プッシュされます

② ループ本体内で、ノードがポップアップされ、ノードに割り当てられるたびに
③ ノードがまだスタックの先頭ノードと等しい場合、それはノードの子がまだ操作されていないことを意味し、その子はスタックに追加される必要があります
④ それ以外の場合は、これは、ノードが 2 回目にポップアップし、ノードにアクセスされることを意味します。

つまり、最初にポップアップしたときにノードの子をスタックにプッシュし、2回目にポップアップしたときにノードにアクセスします

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

この記事のケースを読んだ後、あなたは方法をマスターしたと思います。さらにエキサイティングな内容については、他の php 中国語 Web サイト関連の記事にご注意ください。

推奨読書:

Angularを使用してデータリクエスト機能を実装する方法

vue-cliパッケージ化プロセスでの一般的な問題の処理

以上がJSを使用してDOMツリートラバーサルを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。