This time I will show you how to use JS to implement DOM tree traversal. What are the precautions for implementing DOM tree traversal with JS? 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; }
Preorder traversal
First visit the root node point, then traverse the left subtree, and finally traverse the right subtreeTree.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); } }
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
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); } }
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); } }
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 wayTree.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, 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();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的) } };
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 wayNon-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.
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); } }
How to use Angular to implement the data request function
Handling of common problems in the vue-cli packaging process
The above is the detailed content of How to implement DOM tree traversal using JS. For more information, please follow other related articles on the PHP Chinese website!