What are the methods for JS to implement DOM tree traversal?-JS Tutorial-php.cn

What are the methods for JS to implement DOM tree traversal?

php中世界最好的语言

Release： 2018-05-31 10:20:42

Original

1522 people have browsed it

This time I will bring you some methods to implement DOM tree traversal with JS, and notes to implement traversal with JS on DOM tree. The following is a practical case, let’s take a look.

Binary DOM tree traversal

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

Copy after login

Preorder traversal

First visit the root node point, 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);
  }
}

Copy after login

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

Copy after login

In-order traversal

Traverse the left subtree first 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);
  }
}

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

Depth-first traversal

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

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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!