点击下载
本文文档

当前位置：首页 - 科技 - 知识百科 - 正文

怎样用JS实现DOM树遍历

来源：动视网责编：小采时间：2020-11-27 19:47:39

怎样用JS实现DOM树遍历

怎样用JS实现DOM树遍历:这次给大家带来怎样用JS实现DOM树遍历，JS实现DOM树遍历的注意事项有哪些，下面就是实战案例，一起来看一下。二叉 DOM 树的遍历function Tree() { var Node = function(key){ this.key = key; this.left = null; this.righ

推荐度：

点击下载本文 文档为doc格式

导读怎样用JS实现DOM树遍历:这次给大家带来怎样用JS实现DOM树遍历，JS实现DOM树遍历的注意事项有哪些，下面就是实战案例，一起来看一下。二叉 DOM 树的遍历function Tree() { var Node = function(key){ this.key = key; this.left = null; this.righ

这次给大家带来怎样用JS实现DOM树遍历，JS实现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);
 }
}

相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！

怎样用JS实现DOM树遍历

推荐度：

点击下载本文 文档为doc格式

标签：实现 js 怎么

热门焦点

怎样用JS实现DOM树遍历

怎样用JS实现DOM树遍历

怎样用JS实现DOM树遍历

最新推荐

猜你喜欢

热门推荐