Summary of JS operation DOM tree traversal methods

This time I will bring you a summary of the JS operation DOM tree traversal method, what are the precautions for JS operation DOM tree traversal , the following is a practical case, let's take a look.

The example of this article describes the DOM tree traversal method implemented by JavaScript. Share it with everyone for your reference, the details are as follows:

Traversal of binary DOM tree

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

Preorder traversal

First visit the root node, then traverse the left subtree, and finally traverse the right subtree

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

Modify to DOM binary tree:

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

In-order traversal

First traverse the left subtree, then visit the root node, and finally traverse the right subtree.

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

Modify to DOM binary tree:

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

Post-order traversal

First traverse the left subtree, then traverse the right subtree, and finally visit the root node point.

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

Modify to DOM binary tree:

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

Traversal of multi-fork DOM tree

Breadth-first traversal

First traverse the root node, then visit the first level node, the second level node, ...., until the last level is accessed.

Use the queue to traverse the multi-tree in a non-recursive way

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

First Traverse the root node, then traverse along a path to the deepest level, and finally return level by level.

With the help of stack, depth-first traversal of multi-fork DOM trees is realized.

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

The pre-order, mid-order, and post-order traversal of the binary DOM tree is a special case of depth-first traversal

Therefore, refer to depth-first traversal, with the help of the stack, You can implement pre-order, in-order and post-order traversal of a binary DOM tree in a non-recursive way

Non-recursive implementation of pre-order traversal of a binary DOM tree

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

Non-recursive implementation of in-order traversal of a binary DOM tree

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

Non-recursive implementation of post-order traversal of a binary DOM tree

① Each node is pushed onto the stack twice;
② In the loop body, each time a node is popped up and assigned to node
③ If node is still equal to the head node of the stack, it means that the children of node have not been After the operation, its children should be added to the stack
④ Otherwise, it means that the node is popped up for the second time and the node is accessed.

That is to say, the first time it pops up, push the node's child into the stack, the second time it pops up, access the node

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

I believe you have mastered the method after reading the case in this article, and more How exciting, please pay attention to other related articles on php Chinese website!

Recommended reading:

Detailed explanation of JS callback function use cases

PHP quick implementation of array deduplication method

The above is the detailed content of Summary of JS operation DOM tree traversal methods. For more information, please follow other related articles on the PHP Chinese website!