大发彩票网首页
        当前位置:大发彩票网-建站教程-网站开发-JavaScript/Ajax教程-JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】

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

        文章TAG:JavaScript 遍历 DOM树
        时间:2018-05-07来源:大发彩票网 www.lhltmj.com 作者:源码库 文章热度:

        大发彩票网 www.lhltmj.com 本文实例讲述了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/Ajax教程
        热门标签

        JavaScript/Ajax教程Rss订阅JavaScript/Ajax教程搜索

        大发彩票网官网 | 大发彩票网平台 |
      • 【网易彩票】浮世绘的演进:从汉代中国到现代日本 2018-11-01
      • 【走势图】【广之旅】台湾个人旅游自由行入台证(全国受理) 2018-11-01
      • 【北京福彩网】新浪体育评现役50大第50-41:火箭超6携小曼巴 2018-11-01
      • 【常见问题】日常系列 科普某知名七大兽人氏族杂谈 2018-11-01
      • 【中奖新闻】暗黑时光手游下载v1.0.2 暗黑时光手游官方下载 2018-11-01
      • 【体彩P3】红色警戒2实用攻略秘籍 2018-11-01
      • 【开奖对应】ccleaner中文版|CCleaner(系统垃圾清理工具cc清理器下载)V5.46.0.6652绿色中文版下载 2018-11-01
      • 【彩票开奖直播信息】【新年小黑块】新年小黑块小游戏 2018-11-01
      • 【赔率中心】笔记本系统重装教程,笔记本电脑u盘启动盘装系统教程 2018-11-01
      • 【彩票工具】铁观音为什么要冷藏 因为这个原因 2018-11-01
      • 【上海体彩网】体验这款记录仪后 我发现了路趣T8的秘密【图】 2018-11-01
      • 【北京福彩网】设备维保技术服务工程师SE 2018-11-01
      • 【彩票工具】粉丝探访大熊猫食品专供基地 亲手采摘新鲜竹笋 2018-11-01
      • 【百度彩票】35年梦想成真,秘鲁闯进世界杯 2018-10-30
      • 【中奖信息】如何选佛山吉祥号码,手机号,座机号,终身受用。 2018-10-30