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

网络编程 2024/11/17 佚名

3 1 2

本文实例讲述了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树,遍历

华山资源网 Design By www.eoogi.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

华山资源网 Design By www.eoogi.com

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

暂无评论...

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新日志

2024年11月17日

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

详解VUE-地区选择器(V-Distpicker)组件使用心得

Vue 实现树形视图数据功能

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

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

更新日志

友情链接