【小算法】将数组处理成树状结构

前言

将数组处理成树状结构，也是在工作中经常遇到的，今天就和大家一起分享一下思路和方法。

案例

如下代码，处理成树状结构，要求程序具有容错能力，也就是可以判断输入出错。

let haoroomsDataArr = [
  { id: 1, name: "haorooms1" },
  { id: 2, name: "haorooms2", parentId: 1 },
  { id: 4, name: "haorooms4", parentId: 3 },
  { id: 3, name: "haorooms3", parentId: 2 },
  { id: 8, name: "haorooms18", parentId: 7 },
];

思路

要求处理成树状结构，那么肯定有根节点，从根节点延伸出对应的children,然后再看子节点是否有子节点。

1、首先找出根节点，没有parentId的就是根节点

2、有父节点的均为子节点，根据关联的父节点，设置到一个父节点的对象数组中。

3、针对同一个父节点的子节点数组，因为关联的父节点是惟一的。可以把父节点作为键，所有子节点放到键值对中。

4、根据节点的id,查找以节点id为建的children数组，递归查找是否都有子节点，没有就是leaf节点，或者children为null

异常

1、父节点不存在

2、无子节点（叶子节点）

代码

function getTree(arr) {
  if (!arr || !Array.isArray(arr)) return "错误的数据类型";
  var len = arr.length;
  if (!len) return "空数组";
  var rootObj = { id: null, name: null, children: [] };
  var nodeObj = {};
  for (var i = 0; i < len; i++) {
    if (!arr[i].parentId) {
      rootObj = {
        id: arr[i].id,
        name: arr[i].name,
        children: [],
      };
    } else {
      if (nodeObj.hasOwnProperty(arr[i].parentId)) {
        nodeObj[arr[i].parentId].children.push(arr[i]);
      } else {
        nodeObj[arr[i].parentId] = {};
        nodeObj[arr[i].parentId].children = [];
        nodeObj[arr[i].parentId].children.push(arr[i]);
      }
    }
  }
  function getChildren(node) {
    if (nodeObj[node.id] && nodeObj[node.id].children) {
      node.children = nodeObj[node.id].children;
      delete nodeObj[node.id];
      var len = node.children.length;
      if (len > 0) {
        for (var i = 0; i < len; i++) {
          getChildren(node.children[i]);
        }
      }
    } else {
      console.log(`${node.id}没有children`);
    }
  }
  getChildren(rootObj);

  for (var p in nodeObj) {
    if (nodeObj.hasOwnProperty) {
      console.warn(p + ":没有该父节点");
    }
  }
  return rootObj;
}

方法二

const buildTree = (data, config = {}) => {
  if (!data || !Array.isArray(data)) return "错误的数据类型";
  const len = data.length;
  if (!len) return "空数组";
  const id = (config && config.id) || "id";
  const pid = (config && config.pid) || "parentId";
  const children = (config && config.children) || "children";

  // 把所有的ID映射为一个map 方便查询
  const idMap = {};
  // 找到父节点的放入 treeData
  const treeData = [];
  // 节点包含 pid 属性, 并且父节点不存在的放入 errorData
  const errorData = [];

  data.forEach((v) => {
    v && (idMap[v[id]] = v);
  });

  data.forEach((v) => {
    if (v) {
      let parent = idMap[v[pid]];
      if (parent) {
        !parent[children] && (parent[children] = []);
        parent[children].push(v || []);
      } else if (!parent && v.hasOwnProperty(pid)) {
        errorData.push(v);
      } else {
        treeData.push(v);
      }
    }
  });
  // 树结构 错误数据同时返回
  // return {
  //   treeData,
  //   errorData
  // }
  // 只返回树结构
  return treeData;
};

B站推荐视频推荐

本人开通了B站账号，定期更新前端视频，欢迎关注！

1、js的proto和prototype区别

2、秒懂js的constructor