文档章节

js实现数组转树结构的递归与非递归实现

 甜酒0917
发布于 2016/12/01 13:57
字数 651
阅读 62
收藏 0

递归实现(保存对象属性值,并添加children和levelOnTheTree的属性)

function _initDomTreeObject(ary,data){   
    var data=data?data:(function(ary){
      var tempAry=[];
    var idList=[];
    ary.forEach(function(item){idList.push(item.id)});    
      for(var i=0,len=ary.length;i<len;i++){
        if(ary[i].pid==undefined||(ary[i].pid!=undefined&&deb(ary[i].pid,idList))){
          var obj=ary[i];
          tempAry.push(obj);
        }
       }
        return tempAry; 
    }(ary));
    
  function deb(id,idList){
     var flag=true;
    for(var ida in idList){
      if(id==idList[ida]){
        flag=false;
      }   
    }
     return flag;
   }
  function getParentNode(id,ary){ 
    var parentNode;
    ary.forEach(function(item){
      if(item.id==id){
        parentNode=item;
        return false;
      }
    });
    return parentNode;
  }
   
   function getLevelOnTheTree(ary,dataItem){
     var idList=[];
     ary.forEach(function(item){idList.push(item.id)});
     var level=1;
     while(!deb(dataItem.pid,idList)){
       dataItem=getParentNode(dataItem.pid,ary)
       level++;
     }
      return level;   
   } 

    var temp=0;
   if(data.constructor==Array){
     for(var i=0,len=data.length;i<len;i++){
        for(var j=0,lenA=ary.length;j<lenA;j++){
           if(ary[j].pid==data[i].id){
       var obj=ary[j];
           data[i].children=data[i].children||[];
           data[i].children.unshift(obj);
       temp++;
       }
     }
    }
   }
  

     if(data.constructor==Array){
      for(var n=0,lenB=data.length;n<lenB;n++){
      data[n].levelOnTheTree=getLevelOnTheTree(ary,data[n]);
      if(temp>0){
        data[n].children=_initDomTreeObject(ary,data[n].children?data[n].children:[]);
    if(data[n].children.length==0){
      delete data[n].children;
    }
       }
      } 
    }

  return data;
}

非递归实现 (保存对象属性值,并添加children和levelOnTheTree的属性)

var aaa= [{name:'aaa',id:0},{name:'a',id:1},{name:'b',id:2,pid:1},{name:'c',id:3,pid:1},{name:'d',id:4,pid:2},{name:'e',id:5,pid:2}];

function _initDomTreeObject(sourceAry,data){   
//保存原始数组,以便做比较(不修改原始数据)  
  var ary=[];
  for(var i=0,len=sourceAry.length;i<len;i++){    
    ary[i]=sourceAry[i];
  }
    var data=data?data:(function(ary){
    var tempAry=[];
    var idList=[];
//取得一级菜单,兼容pid为空不存在等各种情况    
    ary.forEach(function(item){idList.push(item.id)});    
      for(var i=0,len=ary.length;i<len;i++){
        if(ary[i].pid==undefined||(ary[i].pid!=undefined&&deb(ary[i].pid,idList))){
          var obj=ary[i];
          ary[i]=null;
//设定一级菜单的层次          
          obj.levelOnTheTree=getLevelOnTheTree(sourceAry,obj);
          tempAry.push(obj);
        }
       }
        return tempAry; 
    }(ary));
//内部方法,用来比较判断    
  function deb(id,idList){
     var flag=true;
    for(var ida in idList){
      if(id==idList[ida]){
        flag=false;
      }   
    }
     return flag;
   }
  //返回父亲节点 
  function getParentNode(id,ary){ 
    var parentNode;
    ary.forEach(function(item){
      if(item.id==id){
        parentNode=item;
        return false;
      }
    });
    return parentNode;
  }
//通过循环判断结点的层次等级   
   function getLevelOnTheTree(ary,dataItem){
     var idList=[];
     ary.forEach(function(item){idList.push(item.id)});
     var level=1;
     while(!deb(dataItem.pid,idList)){
       dataItem=getParentNode(dataItem.pid,ary)
       level++;
     }
      return level;   
   }  

//非递归的核心算法
   function getSelfDom(itemAry,data){
     var  flag=false;
     var  len=data.length;

     for(var i=0;i<data.length;i++){
     console.log("长度",data.length)
       if(itemAry.pid==data[i].id){    
       flag=true;
       data[i].children=data[i].children||[];
//设置各节点的层次级别      
       itemAry.levelOnTheTree=getLevelOnTheTree(sourceAry,itemAry);    
       data[i].children.push(itemAry);
      }else{
        data[i].children&&(data=data.concat(data[i].children));
      
      }    

      if(flag){
 //如果有多个父亲,只找第一个父亲 ,不写此处的话兼容多父亲模式        
        break;
       }
     }
     return {
               flag:flag,
               data:data.slice(0,len)
             };
 }

//非递归的循环出口
   while(ary.length>0){ 
       var itemAry=ary.shift();
       if(itemAry!=null){
       var obj=getSelfDom(itemAry,data);
       if(obj.flag){
            data=obj.data;
       }else{
         ary.push(itemAry);
       }
     }
   }
  return data;
}

var a=_initDomTreeObject(aaa);
  console.log(a)

 

© 著作权归作者所有

共有 人打赏支持
粉丝 1
博文 13
码字总数 3450
作品 0
武汉
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
Ztree + PHP 无限级节点 递归查找节点法

一、前言 简单的描述一下,实习几个原理,思想,其实写很多东西,思想算是最重要的。 1、目标:将写一个无限节点的树形目录结构,如下图 步骤: 1、你的下载 插件 ztree。然后布置在你的项目...

RablePHP
2014/11/14
0
7
js vis vue 实现AVL树

AVL树,插入和删除节点, 不同的旋转实现 参考 http://blog.csdn.net/zhangxiangdavaid/article/details/37115355 js: 二叉树的三种遍历递归实现与非递归实现,删除采用中序遍历重新创建.....懒...

阿豪boy
2017/11/01
0
0
JavaScript专题之递归

JavaScript 专题系列第十八篇,讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例: 示意图(图片来自 wwww.penjee.com): 斐波那契数列 在《JavaScript专...

冴羽
2017/09/13
0
0
JavaScript 编程精解 中文第三版 十二、项目:编程语言

十二、项目:编程语言 原文:Project: A Programming Language 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 部分参考了《JavaScript 编程精解(第 2 版)》 确定编程语言中的表达式...

ApacheCN_飞龙
05/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker-compose ,docker-stack

1.例子 version: "3"services: php: image: registry.cn-hangzhou.aliyuncs.com/lxepoo/apache-php5 ports: - "38080:80" networks: - my_php_mysql volum......

chenbaojun
28分钟前
1
0
SQL_Server2000示例数据库NorthWind的分析(转)

SQL_Server2000示例数据库NorthWind的分析 表名:Categories(食品类别表) 表结构: 字段名称 数据类型 长度 允许为空 CategoryID(主键) int 4 否 CategoryName nvarchar 15 否 Description ...

QQZZFT
30分钟前
1
0
laravel 5.5 Session store not set on request.

laravel 5.5 数据存入session,会出现Session store not set on request.错误。查了下laravel 5.5将session放到global middleware中,需要laravel的文件 ./app/Http/Kernel.php中的加上一句:...

MichaelShu
今天
1
0
OpenCV VideoCapture.get()参数详解

param define cv2.VideoCapture.get(0) 视频文件的当前位置(播放)以毫秒为单位 cv2.VideoCapture.get(1) 基于以0开始的被捕获或解码的帧索引 cv2.VideoCapture.get(2) 视频文件的相对位置(...

NateHuang
今天
0
0
java基础知识,小栗子

来操作一下数组.....注意带参数的变长数组的使用. package com.avatus;import java.util.Random;import java.util.Scanner;public class Main { public static void main(St...

Oh_really
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部