【手写系列】手把手教你如何实现列表转树-树转列表

技术分享 3年前 (2023-08-01) 0 999+

关注

这个应该算是前端中经常出现的业务场景，不过大部分都是由组件库帮助你做好了这些事情

如果要是让你自己来实现，你又会如何实现呢?

今天，我们就来好好讲解下这两个需求该如何去写，在知道如何用的情况下，也要知道如何实现它们。

从这篇文章你能学到(复习)什么东西

JS中Map的用法
递归解法
hasOwnProperty
JSON.Stringify
JSON.parse

树转列表该如何实现

这个使用场景应该是较为常见的，如果给你一个树结构，需要你从中搜索到某一子项，你就可以这样做。

直接将树结构转成列表，那么搜索起来的效率也会比较高，时间复杂度就是O(n)

我目前能想到的解法是-深度遍历，代码实现如下

const tree = [   {     id: 1,     name: "部门1",     pid: 0,     children: [       {         id: 2,         name: "部门2",         pid: 1,       },       {         id: 3,         name: "部门3",         pid: 1,         children: [           {             id: 4,             name: "部门4",             pid: 3,             children: [               {                 id: 5,                 name: "部门5",                 pid: 4,               },             ],           },         ],       },     ],   },   {     id: 6,     name: "部门6",     pid: 0,   }, ];  const transformTreeToList = (tree) => {   const result = [];   const fn = (tree) => {     for (const item of tree) {       result.push({         id: item.id,         name: item.name,         pid: item.pid,       });       if (!item.children || item.children.length === 0) continue;       fn(item.children);     }   };   fn(tree);   return result; };  const data = transformTreeToList(tree); console.log("列表数据", data);

我们从transformTreeToList这个函数开始看。

首先需要对树进行遍历，最关键的步骤是判断当前项是否有孩子，有孩子的话，则需要进入下一层，没有的话则需要进入到下一次，不执行fn(item.children)

整体来讲，这个数转列表比较好写，类似与这种递归解法，最重要的核心是找到结束条件

不知道大家有没有更好的解决办法呢，有的话欢迎评论留言(～￣▽￣)～

列表转树该如何实现

在列表转树，提供给你一个带有pid对象，这个pid就是指向它的上一层的id。

在我们实现嵌套层级展示的时候，列表转树就非常有用了。

接下来，来看下我是怎么实现的~

let arr = [   { 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: 0 }, ];  const listToTree = (list) => {   const hashMap = new Map();   // 深拷贝原始数据，防止我们的修改影响原始数据   const newList = JSON.parse(JSON.stringify(list));   // 将数据全部存入到map中去   newList.forEach((item) => {     hashMap.set(item.id, item);   });   newList.forEach((item) => {     if (hashMap.has(item.pid)) {       const parent = hashMap.get(item.pid);       if (parent.hasOwnProperty("children")) {         parent.children.push(item);       } else {         parent.children = [item];       }     }   });    return newList.filter((item) => item.pid === 0); };  console.log(listToTree(arr), arr);

是不是看上去比较简单，这种解法应该是最优解了，如果大家还有其他解法，欢迎在评论区留言。

我们来分析下。

1️⃣ 我们需要用到Map，Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值（对象或者基本类型）都可以作为一个键或一个值。

2️⃣ 我们先将列表数据依次存入到Map对象中去，列表的数据id作为key，列表的数据整体作为值。

3️⃣ 然后我们需要newList在进行遍历，这一次主要是判断在map中是否有对应的pid的值，如果有的话，则说明，当前项是属于id为pid的孩子，我们就需要将当前值放到id为pid的对象中去。

4️⃣ 在这样操作完之后，我们需要过滤出pid为0的值，因为pid为0意味着它是第一级，也是我们需要的数据。

总结一下，其实我们是利用了 Map的取值的时间复杂度是O(1), 无需遍历，效率比较高，我们只用了一次循环，就可以把这个项放到对应的父亲下面。

💫恭喜你们，看到这里，你们对这两个手写有没有明白呢，如果有不明白的，欢迎在评论区留言。