JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】

2024-05-06 16:44:09

字体：大中小

来源：转载

供稿：网友

本文实例讲述了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/Ajax教程频道。

上一篇：JavaScript 跨域之POST实现方法

下一篇：JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】