Summary of JS operation DOM tree traversal methods-JS Tutorial-php.cn

This time I will bring you a summary of the JS operation DOM tree traversal method, what are theprecautions 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 byJavaScript. 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; }

Copy after login

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

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

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

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-recursiveway

Tree.prototype.BFSearch = function(node,callback){ var queue=[]; while(node!=null){ callback(node); if(node.children.length!=0){ for (var i=0;i
        
         Copy after login

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

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!