【算法解析】js 扁平数据转树形数据

用户9914333

发布于 2022-07-22 14:03:41

1.7K0

文章被收录于专栏：bug收集bug收集

在项目开发过程中，都会遇到树形数据结构与扁平数据结构的转换。

今天就分享一下，扁平数据结构转树形数据结构的方法

回顾数据结构

扁平数据结构

[{id:1, pid:0, name:'沃尔玛'},
 {id:2, pid:1, name:'生鲜区'},
 {id:3, pid:1, name:'日用品区'},
 {id:4, pid:2, name:'鱼'},
 {id:5, pid:2, name:'牛肉'},
 {id:6, pid:3, name:'卫生纸'},
 {id:7, pid:3, name:'牙刷'},
 {id:8, pid:7, name:'电动牙刷'},
 {id:9, pid:7, name:'普通牙刷'}]

树形数据结构

[{id:1, pid:0, name:'沃尔玛', childrens:[
      {id:2, pid:1, name:'生鲜区', childrens:[
        {id:4, pid:2, name:'鱼'},
        {id:5, pid:2, name:'牛肉'}
      ]},
      {id:3, pid:1, name:'日用品区',childrens:[
          {id:6, pid:3, name:'卫生纸'},
          {id:7, pid:3, name:'牙刷'}
        ]}
    ]}

扁平转树形

核心思想：

就是使用了Map来存储不同的id,对应的所在的内存地址，根据对应pid的值，找到你要加入到对象对应的位置。

思路 ( 递归方法 )：

1、申明一个Map对象，pid，outputObj三个变量

 var map = new Map(); //存在id,对应所在的内存地址
 var outputObj,pid;

2、循环数组，取出每个对象对应的pid

 for(var i = 0; i<data.length;i++){
        pid = data[i].pid;

3、判断对应的pid是否已经存在Map中，如果存在，判断childrens属性是否存在，不存在，创建一个childrens属性; 将当前对象克隆到一个新对象，加入到childrens中。并且，将当前对象的id加入到Map中(重点)

 if(map.has(pid)){
   //存在，将此信息，加入到对应id=pid的对象上的children
   if (!map.get(pid).childrens) //添加childrens属性
          map.get(pid).childrens = [];
   var obj = new Object(data[i]);
   map.get(pid).childrens.push(obj);
   //通过pid在Map中查找，并将当前对象，加入到对应的childres属性
   map.set(data[i].id,obj); 
   //重点(必须也加入Map)：将当前id及对应的对象，存入Map对象中
 }

4、判断pid不在Map中存在，并且pid为0；创建一个新的对象，且将id存入Map中

 else if(!map.has(pid)&&pid==0){
   //这里处理pid不存在，且pid 为0的处理，pid不存在，且不为0的，程序不考虑这种情况
   outputObj = new Object(data[i]);
   map.set(data[i].id,outputObj);
   //将id添加到Map中
   TreeData.push(outputObj); 
   //加入到要返回的数组中
 }

完整代码如下：

function GetTreeData(data){
        var TreeData=[];
        var map = new Map(); //存在id,对应所在的内存地址
        var outputObj,pid;
        for(var i = 0; i<data.length;i++){
            pid = data[i].pid;
            if(map.has(pid)){
                //存在，将些信息，加入到对应id=pid的对象上的children
                if (!map.get(pid).childrens)
                    map.get(pid).childrens = [];
                var obj = new Object(data[i]);
                map.get(pid).childrens.push(obj);
                map.set(data[i].id,obj);
            }else if(!map.has(pid)&&pid==0){
                //这里处理pid不存在，且pid 为0的处理，pid不存在，且不为0的，程序不考虑这种情况
                outputObj = new Object(data[i]);
                TreeData.push(outputObj);
                map.set(data[i].id,outputObj);
            }
        }
        return TreeData;
    }

示例代码

写了一个DEMO

若pid对应的值，id没有，使用上面的转换方法，将忽略这条数据;

如下：{id:6, pid:13, name:'卫生纸'}

代码如下：

var data=[{id:1, pid:0, name:'沃尔玛'},
        {id:2, pid:0, name:'生鲜区'},
        {id:3, pid:1, name:'日用品区'},
        {id:4, pid:2, name:'鱼'},
        {id:5, pid:2, name:'牛肉'},
        {id:6, pid:13, name:'卫生纸'},
        {id:7, pid:3, name:'牙刷'},
        {id:8, pid:7, name:'电动牙刷'},
        {id:9, pid:7, name:'普通牙刷'}];
    var TreeData = GetTreeData(data);
    console.log(TreeData);
    function GetTreeData(data){
        var TreeData=[];
        var map = new Map(); //存在id,对应所在的内存地址
        var outputObj,pid ;
        for(var i = 0; i<data.length;i++){
            pid = data[i].pid;
            if(map.has(pid)){
                //存在，将些信息，加入到对应id=pid的对象上的children
                if (!map.get(pid).childrens)
                    map.get(pid).childrens = [];
                var obj = new Object(data[i]);
                map.get(pid).childrens.push(obj);
                map.set(data[i].id,obj);
            }else if(!map.has(pid)&&pid==0){
                //这里处理pid不存在，且pid 为0的处理，pid不存在，且不为0的，程序不考虑这种情况
                outputObj = new Object(data[i]);
                TreeData.push(outputObj);
                map.set(data[i].id,outputObj);
            }
        }
        return TreeData;
    }

‍

本文分享到这，关于树形结构转扁平结构，请看下面文章

【算法解析】js 树形数据转扁平数据

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构