大发彩票网首页
        当前位置:大发彩票网-建站教程-网站开发-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-09-19
      • 曝詹姆斯邀请杜兰特同去湖人 但遭后者拒绝 2018-09-19
      • 74家财险公司净利润不足6亿元 2018-09-19
      • 长生生物被证监会立案调查 2018-09-19
      • 国企改革"双百行动"正式启动 下半年有望明显提速 2018-09-19
      • “吃鸡”手游现“731部队” 韩开发商下架道歉 2018-09-16
      • 多省不动产登记联网提速 专家称房地产税渐近 2018-09-16
      • 上半年居民消费榜出炉 安徽人均支出8482元排名15 2018-09-16
      • 鍩庡競鍥犱綘鑰屽噣 娴峰皵鍑€姘翠笌浣犱竴璧蜂笀閲忓煄甯傛枃鏄庘€斺€斿噣鍗冭矾 鏆栦竴鍩?鍏泭鍦ㄨ鍔 2018-09-16
      • 为啥卖药的都爱上了P2P? 2018-09-16
      • 烟台市拨付台风灾害救助资金630万元 2018-09-15
      • 浪潮软件(600756)融资融券 2018-09-15
      • 2018未来科学大奖公布:袁隆平李家洋等获奖—新闻—科学网 2018-09-15
      • 航拍巴山大峡谷 探索川东大地的奇妙瑰宝 2018-09-15
      • 河南省公布第一批“一网通办”前提下“最多跑一次”审批服务事项目录最大限度利企便民 2018-09-15