JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】
本文实例讲述了JavaScript实现的DOM树遍历方法。分享给大家供大家参考，具体如下：
二叉DOM树的遍历
functionTree(){
varNode=function(key){
this.key=key;
this.left=null;
this.right=null;
}
root=null;
}
前序遍历
首先访问根结点，然后遍历左子树，最后遍历右子树
Tree.prototype.preOrderTraverse=function(callback){
preOrder(root,callback);
}
varpreOrder=function(node,callback){
if(node!==null){
callback(node.key);
preOrder(node.left,callback);
preOrder(node.right,callback);
}
}
修改为DOM二叉树：
varpreOrder=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);
}
varinOrder=function(node,callback){
if(node!==null){
inOrder(node.left,callback);
callback(node.key);
inOrder(node.right,calback);
}
}
修改为DOM二叉树：
varinOrder=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);
}
varpostOrder=function(node,callback){
if(node!==null){
postOrder(node.left,callback);
postOrder(node.right,calback);
callback(node.key);
}
}
修改为DOM二叉树：
varpostOrder=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){
varqueue=[];
while(node!=null){
callback(node);
if(node.children.length!=0){
for(vari=0;i
深度优先遍历
首先遍历根节点，然后沿着一条路径遍历到最深的一层，最后在逐层返回。
借助于栈,实现多叉DOM树的深度优先遍历。
Tree.prototype.DFSearch=function(node,callback){
varstack=[];
while(node!=null){
callback(node);
if(node.children.length!=0){
for(vari=node.children.length-1;i>=0;i--){//按照相反的子节点顺序压入栈
stack.push(node.children[i]);//将该节点的所有子节点压入栈
}
}
node=stack.pop();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)
}
};
二叉DOM树的前序、中序、后序遍历，是深度优先遍历的特例
因此，参考深度优先遍历，借助栈，可以以非递归的方式，实现二叉DOM树的 前序、中序和后序遍历
非递归实现二叉DOM树的前序遍历
Tree.prototype.preOrder=function(node,callback){
varstack=[];
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){
varstack=[];
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){//非递归实现
varstack=[];
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程序设计有所帮助。