前端JS扁平化数据处理转换成Tree树形结构

前言

 

 

无论在实际开发中还是面试时对数据结构的处理都是十分的重要。好的数据处理方式可以大大提高程序的运行速度。

面试时我们也会经常遇到下面这种扁平化数据处理的问题，具体内容如下：

 

有下面一组扁平化数据：

 

let data = [
  { id: 1, name: "组织1", pid: 0 },
  { id: 2, name: "组织2", pid: 1 },
  { id: 3, name: "组织3", pid: 1 },
  { id: 4, name: "组织4", pid: 3 },
  { id: 5, name: "组织5", pid: 4 },
  { id: 6, name: "组织6", pid: 5 },
];

 

现在需要将这组数据转化成下面这种格式：

 

[
  {
    id: 1,
    name: "组织1",
    pid: 0,
    children: [
      { id: 2, name: "组织2", pid: 1, children: [] },
      {
        id: 3,
        name: "组织3",
        pid: 1,
        children: [
          {
            id: 4,
            name: "组织4",
            pid: 3,
            children: [
              {
                id: 5,
                name: "组织5",
                pid: 4,
                children: [{ id: 6, name: " 组织6", pid: 5, children: [] }],
              },
            ],
          },
        ],
      },
    ],
  },
];

 

这种数据的处理很多人首先想到的很可能是递归的方法，但这种方法效率比较慢，时间复杂度较高（O(2^n)），不建议使用。下面总结了两种新的处理方法。

 

 

扁平化数据处理，方法一：

第一种是使用两组循环遍历的方法。第一次遍历将原数组转换成对象的形式，方便处理数据；第二次遍历是真正的数据处理过程。具体代码如下：

 

function conversion1(data) {
  let obj = {};
  let res = [];
  //第一次遍历 将数组转换成对象 方便操作
  data.forEach((item) => {
    // 使用赋值的方式转换，使新对象中每个值的引用地址和数组中的值一一对应
    obj[item.id] = item;
    obj[item.id].children = [];
  });

  // 第二次遍历 将扁平化数据转换成tree
  data.forEach((item) => {
    if (item.pid === 0) {
      res.push(obj[item.id]);
    } else {
      //  若item的引用地址不能和arr对象中对应数据的地址相同，则无法通过地址引用生成新的完整的树
      obj[item.pid].children.push(item);
    }
  });
  return res;
}

 

实现原理：

（1）先将原数组进行遍历生成新的对象，要确保新对象obj中每个属性对应值的引用地址和原数组中的数据一一对应，方便后面进行“地址传递”；

（2）第二次遍历，通过判断每个数据的pid是否为0来判断该数据是否为根数据。若该数据是跟对象则直接将该对象push到新的数组中，若不是则将该对象的存到obj[pid]的children属性中。遍历结束后，原数组中的数据就可以通过地址引用的方式依次按照对应的父子关系联系起来。

 

注意事项：

第一次转换成对象时不要使用“...”展开符，这样会生成新的地址，新生成的对象对应的数据和原数组数据不是指向同一个地址，从而无法引用正确的数据，最终会得到如下的结果：

 

[
	{
		id: 1,
		name: "组织1",
		pid: 0,
		children: [
			{ id: 2, name: "组织2", pid: 1, children: [] },
			{ id: 3, name: "组织3", pid: 1, children: [{ id: 4, name: "组织4", pid: 3, children: [{ id: 5, name: "组织5", pid: 4, children: [{ id: 6, name: "组织6", pid: 5, children: [] }] }] }] }
		]
	}
];

 

 

扁平化数据处理，方法二：

第二种方法仅使用一次遍历就可以完成数据的处理。

实现原理：

首先和第一种方法相似，将数组中的所有数据复制在新的对象中，此时可以使用展开符（...）展开，具体原因可以自己进行分析。然后通过判断每组数据是否为根数据（pid = 0），若是则直接存入新的数组中，若不是则将该数据存到obj[pid]的children属性中。遍历结束后依旧通过地址引用关联到所有数据，最后得到想要的结果。

 

注意：该方法有一定的局限性，即要求父属性必须在前。这意味着如果数据中子节点出现在父节点之前，则该方法可能无法正确地构建树形结构。

function conversion2(data) {
  const res = [];
  const obj = {};
  data.forEach((item) => {
    const id = item.id;
    const pid = item.pid;

    obj[id] = {
      ...item,
      children: [],
    };

    if (pid == 0) {
      res.push(obj[id]);
    } else {
      obj[pid].children.push(obj[id]);
    }
  });
  return res;
}

 

扁平化数据处理，方法三：

实现原理：

（1）先将原数组进行遍历生成新的数组，要确保新数组中每个元素的引用地址和原数组中的数据一一对应，方便后面进行“地址传递”；

（2）通过判断stack中是否存在数据进行遍历。每次删除最后一个元素并和元数据比较找出其父元素，并将该元素添加到其父元素的children属性中。如果不存在父元素则将该元素push到结果数组中。

 

function flatData1(data: any) {
  const result: any = []
  const stack: any = []
  for (let i = 0; i < data.length; i++) {
    stack.push(data[i])
  }
  while (stack.length) {
    const item = stack.pop()
    const parent = data.find((v: any) => v.id === item.pid)
    if (parent) {
      parent.children = parent.children || []
      parent.children.push(item)
    } else {
      result.push(item)
    }
  }
  return result
}

 

 

总结：

这两种方法主要都是使用引用类型数据传递时是通过地址传递的特性，通过对应的关系引入对应数据的地址生成新的数组。第二种方法是第一种方法的优化版本，第一种方式的时间复杂度为O(2n)，空间复杂度为O(n)，第二种方式的时间复杂度为O(n)，空间复杂度为O(n)，第三种方式的时间复杂度为O(n^2)，空间复杂度为O(n)，相比较而言，第二种方法的性能最好，但第二种方法会有局限性。

 

结束语：

后期想到更好的方法再进行补充。