大发彩票网首页
        当前位置:大发彩票网-建站教程-网站开发-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-07-23
      • 前列腺炎 疾病百通 医通无忧网 2018-07-23
      • 重庆旅游投诉热线96111从10月1日起启用 2018-07-23
      • 零售收银软件 在街上为中小实体商家带来新机遇 2018-07-23
      • 重庆公交站一夜惊变玩心酒馆 鼓励“快乐就现在”引共鸣! 2018-07-23
      • 『宝贝启航2018』儿童保险 2018-07-23
      • 启辰D60智联豪华版试驾 升级智能车机 2018-07-23
      • [主题活动 ]土右文明网 2018-07-23
      • 香港马会奖卷有限公司 2018-07-23
      • 翁源县卫计局、残联开展下乡评残活动 2018-07-22
      • 【淄博房地产门户|淄博房产网|淄博房产信息网】 2018-07-22
      • 楼市调控新政初见成效 长沙商品房入市速度加快 2018-07-22
      • 江苏启东福彩启动“慈善圆梦大学”助学活动 2018-07-22
      • 常修泽:增强开拓前进的勇气和力量 2018-07-22
      • ::紫光阁::中共中央国家机关工作委员会 2018-07-22