首页 » 网络编程 » JavaScript

js将列表组装成树结构的两种实现方式分享

JavaScript 2022-01-09

前言

工作中偶尔就会遇到后端同学丢来一个列表,要我们自己组装成一个树结构渲染到页面上,本文以两种不同方式探索生成树的算法思想。

js将列表组装成树结构的两种实现方式分享

背景介绍

可组装成树结构的数组一般有以下几个要素:

  • 当前节点id
  • parentId 当前节点的父节点id
  • children 子节点列表(可能不会在接口中返回,需要组装时候自己加上)

原始结构:

js将列表组装成树结构的两种实现方式分享

目标结构:

js将列表组装成树结构的两种实现方式分享

关键就是一维数组中通过parentId找到其对应的父节点并添加到父节点的children数组中。

实现方案

最直接的方式就是遍历数组,并把找到的子节点逐一添加到父节点中

function listToTreeSimple(data) {
  const res = [];
  data.forEach((item) => {
    const parent = data.find((node) => node.id === item.parentId);
    if (parent) {
      parent.children = parent.children || [];
      parent.children.push(item);
    } else {
      // * 根节点
      res.push(item);
    }
  });
  return res;
}

考虑进一步优化,使用哈希表,以id为key存储每个节点值,省去data.find计算

function listToTree(data) {
  // * 先生成parent建立父子关系
  const obj = {};
  data.forEach((item) => {
    obj[item.id] = item;
  });
  // * obj -> {1001: {id: 1001, parentId: 0, name: 'AA'}, 1002: {...}}
  // console.log(obj, "obj")
  const parentList = [];
  data.forEach((item) => {
    const parent = obj[item.parentId];
    if (parent) {
      // * 当前项有父节点
      parent.children = parent.children || [];
      parent.children.push(item);
    } else {
      // * 当前项没有父节点 -> 顶层
      parentList.push(item);
    }
  });
  return parentList;
}

即便数据量很小,带来的性能提升也是显著的

js将列表组装成树结构的两种实现方式分享

递归法

更有骚操作递归法,性能会很差,但代码会很酷??

function recursiveToTree(data) {
  function loop(key) {
    const arr = [];
    data.forEach((item) => {
      if (item.parentId === key) {
        item.children = loop(item.id);
        arr.push(item);
      }
    });
    return res;
  }
  return loop(1);
}

看看性能,诶?看起来竟然递归性能最佳??

js将列表组装成树结构的两种实现方式分享

但是数据量稍微大一点……

js将列表组装成树结构的两种实现方式分享

(上面递归,下面非递归)

资源

原始数据列表

const list = [
  {
    id: 1001,
    parentId: 0,
    name: "AA",
  },
  {
    id: 1002,
    parentId: 1001,
    name: "BB",
  },
  {
    id: 1003,
    parentId: 1001,
    name: "CC",
  },
  {
    id: 1004,
    parentId: 1003,
    name: "DD",
  },
  {
    id: 1005,
    parentId: 1003,
    name: "EE",
  },
  {
    id: 1006,
    parentId: 1002,
    name: "FF",
  },
  {
    id: 1007,
    parentId: 1002,
    name: "GG",
  },
  {
    id: 1008,
    parentId: 1004,
    name: "HH",
  },
  {
    id: 1009,
    parentId: 1005,
    name: "II",
  },
];

总结

到此这篇关于js将列表组装成树结构的两种实现方式的文章就介绍到这了,更多相关js列表组装成树结构内容请搜索www.580doc.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.580doc.com!


上一篇:如何利用js根据坐标判断构成单个多边形是否合法下一篇:由?JavaScript?的?with?引发的探索
程序园_程序员的世界 Copyright © 2020- www.580doc.com. Some Rights Reserved.