JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】
本文实例讲述了javascript实现的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 树的遍历
广度优先遍历
首先遍历根节点,然后访问第一层节点,第二层节点,....,直到访问到最后一层。
借助于队列,用非递归的方式对多叉树进行遍历
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 树的后序遍历
① 每个节点,都压入栈两次;
② 在循环体中,每次弹出一个节点赋给node
③ 如果node仍然等于栈的头结点,说明node的孩子们还没有被操作过,应该把它的孩子们加入栈中
④ 否则,说明是第二次弹出该节点,访问node。
也就是说,第一次弹出,将node的孩子压入栈中,第二次弹出,访问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); } }
更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript操作dom技巧总结》、《javascript错误与调试技巧总结》、《javascript数据结构与算法技巧总结》、《javascript遍历算法与技巧总结》及《javascript数学运算用法总结》
希望本文所述对大家javascript程序设计有所帮助。
上一篇: 详解用Docker构建MySQL主从环境
下一篇: php支付宝APP支付功能