算法练习05 生成树形结构的方法

发表于 2019-03-18 分类于算法阅读次数：

由数组生成树形结构的方法。

问题

接受了一个简单小任务，从后端获取一系列数据，以数组的形式存在，每一项都有着id和parentId，根据这两个属性，将这写数组重新组织成为一个树状菜单结构，传递给UI组件

这个问题有一点难度的事，后端传递的数据不是组织好的，是没有顺序的，就是说，有可能子项先出现，而父项后出现

let originId = [ 
  id: 2,
  name: 'b',
  parentId: 0
}, {
  id: 4,
  name: 'a-2',
  parent_id: 1
}, {
  id: 5,
  name: 'b-1',
  parentId: 2
}, {
  id: 6,
  name: 'b-2',
  parentId: 2
}, {
  id: 3,
  name: 'a-1',
  parentId: 1
}, {
  id: 1,
  name: 'a',
  parentId: 0
}, {
  id: 7,
  name: 'a-1-1',
  parentId: 3
}, ];

所以在处理的时候，需要递归处理

递归

实际上，直接用递归是可以实现的，但是我也是在网找了一阵子才发现这种方法，因为一来自己的算法实在是弱，也是因为着急的时候反而脑子更加不好用

//递归方法 生成 json tree 数据
const getJsonTree = function(data, parentIds) {
  var itemArr = [];
  for (var i = 0; i < data.length; i++) {
    var node = data[i];
    if (parentIds.includes(node.parentId)) {
      var newNode = {};
      newNode.id = node.id;
      newNode.name = node.name;
      newNode.children = getJsonTree(data, [node.id]);
      itemArr.push(newNode);
    }
  }
  return itemArr;
};

console.log(getJsonTree(originData, ['0', 'non']))

这种方法能够实现，但是没有任何优化，对originData反复遍历查找，如果数据量很大的时候，恐怕性能上会出问题

利用JavaScript的引用类型

这个纯属是学习了，首先对所有数据进行分组，也就是简历索引，将同一个parentId的数据都放到一个对象的同一个属性名对应的属性值中，也就是说生成这样的结构：

const groupData = {
  // parentId为'0'的数据都在这里
  // 换句话说，id为'0'的所有子数据都在这里
  '0': {
    [1],
    [2]
  }
}

这个还是比较好实现的，一个reduce搞定:

const groupedData = data.reduce((total, current) => {
  total[current['parentId']] ? total[current['parentId']].push(current) : total[current['parentId']] = [current];
  return total;
}, {});

现在，通过groupedData这个对象可以找到某个id对应的所有子数据，那么我就可以认为，对原始数据originData进行遍历，给数据增加一个chilren属性，把对应的groupedData的索引复制到这个children属性

我的脑子还是不太够用，说白了就是蠢，感觉绕在里面出不来，想了好一阵子才理清楚：

const getJsonTree2 = function (data, id) {
  // 按照parentId对所有数据分组
  const groupedData = data.reduce((total, current) => {
    total[current['parentId']] ? total[current['parentId']].push(current) : total[current['parentId']] = [current];
    return total;
  }, {});
  
  // 遍历原始数据，
  data.forEach(v => {
    // 如果当前项的id存在于groupedData中，说明当前项就是groupedData对应的属性中所有元素的父元素
    // 如果当前项的id不存在于groupedData中，说明当前项不是任何元素的父元素，就是个纯纯的子元素
    // ID是不会重复的
    if (groupedData[v.id]) {
      v.children = groupedData[v.id]
    }
  });
  return groupedData[id]
};

最后取出的数据是从groupedData取出顶级元素，传入顶级元素的ID即可，因为这个需求比较特殊，顶级元素有两种ID，'0'或者'non'，所以需要额外处理一下：

return ids.reduce((total, current) => {
  if (groupedData[current]) {
    total = total.concat(groupedData[current]);
  }
  return total;
}, []);

因为这个利用了JS的引用类型，所以不能采用下面的这种形式来改变最终的元素包含的属性：

1
2
3

current = {
  id: node.id
}

因为这会导致引用关系的丢失，所以如果需要改变最终树状元素的包含的属性有两种方法，一种是在分组获取groupedData时，采用下面这种形式直接修改元素属性：

const dealObj = obj => {
  obj.label = obj.chinese;
  delete obj.name;
  delete obj.chinese;
  delete obj.creator;
  delete obj.parentId;
  delete obj.status;
  delete obj.createTime;
  delete obj.updateTime;
};

// 按照parentId对所有数据分组
const groupedData = data.reduce((total, current) => {
  total[current['parentId']] ? total[current['parentId']].push(current) : total[current['parentId']] = [current];
  // 处理元素包含的属性
  dealObj(current);
  return total;
}, {});

也可以在生成最终数据后统一处理，但是这样会增加时间复杂度：

// 处理最终的数据
const dealRes = res => {
  res.forEach(v => {
    dealObj(v);
    if(v.children && v.children.length) {
      dealRes(v.children)
    }
  })
};

dealRes(result);

问题

递归

利用JavaScript的引用类型

参考