本文实例讲述了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程序设计有所帮助。
您可能感兴趣的文章:
- javascript先序遍历DOM树的方法
- JS遍历DOM文档树的方法实例详解
- JavaScript简单遍历DOM对象所有属性的实现方法
- JS中的二叉树遍历详解
- JavaScript实现树的遍历算法示例【广度优先与深度优先】
- JavaScript实现二叉树的先序、中序及后序遍历方法详解
- JS实现二叉查找树的建立以及一些遍历方法实现
- javascript实现二叉树遍历的代码
- JavaScript数据结构之二叉树的遍历算法示例
- JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例
- JavaScript实现二叉树定义、遍历及查找的方法详解