树形结构和平铺结构的转换

1. 前言

不论是在实际的业务还是在面试中，博主都遇到了这样的一个需求。

将一个树形结构的数据转换成平铺的数组，或者将平铺的数组装换成树形结构，因此在这里记录一下如何实现这种转换的思想。

假设存在以下数据，其中 tree 是一个树形结构的数据，从外到内层级结构；arr 是树形结构的数组平铺，其中 pid 指在树形结构中上一层级的 id 值。

const tree = [{id: 1,name: '北京',children: [{id: 11,name: '朝阳',children: [{ id: 111, name: '朝阳1号' }]}, {id: 12,name: '海淀',children: [{ id: 121, name: '海淀1号' }]}]
},{id: 2,name: '上海',children: [{id: 21,name: '浦东',children: [{ id: 211, name: '浦东1号' }]},{id: 22,name: '虹口',children: [{ id: 221, name: '虹口1号' }]}]
}];

const arr = [{ pid: null, id: 1, name: '北京' },{ pid: 1, id: 11, name: '朝阳' },{ pid: 11, id: 111, name: '朝阳1号' },{ pid: 1, id: 12, name: '海淀' },{ pid: 12, id: 121, name: '海淀1号' },{ pid: null, id: 2, name: '上海' },{ pid: 2, id: 21, name: '浦东' },{ pid: 21, id: 211, name: '浦东1号' },{ pid: 2, id: 22, name: '虹口' },{ pid: 22, id: 221, name: '虹口1号' }
]

实现两个方法，让这两种数据可相互转换。

2. 正向-树形结构转平铺

// 正向-树形结构转平铺
// 从外到内依次递归，有 children 则继续递归
function treeToArr(data, pid=null, res=[]) {data.forEach(item => {res.push({ pid: pid, id: item.id, name: item.name });if(item.children && item.children.length !== 0) {treeToArr(item.children, item.id, res);}});return res;
};const arr = treeToArr(data);
console.log(arr);

3. 逆向-平铺结构转树形

// 依次在数组中找到每一层级对应的元素，同时每个元素的 children 属性对应的 value 通过 pid 去找到，然后递归执行下去
function arrToTree(arr, pid=null) {const res = [];arr.forEach(item => {if(item.pid === pid) {// 这样每次都需要遍历整个数组，因此时间复杂度为 n*n// const children = arrToTree(arr, item.id)   // 往下递归时，每次数组的大小都在减小，每次都筛选掉父代元素，最终的时间复杂度为 n*lognconst children = arrToTree(arr.filter(v => v.pid !== pid), item.id);if(children.length) {res.push({ ...item, children })}else {res.push({ ...item })}}});return res;
};const tree = arrToTree(arr);
console.log(JSON.stringify(tree, null, 2));

4. 总结

1. 解决思路

   主要利用递归，正向-树形转平铺由外向内递归；逆向-平铺结构转树形由内向外递归。

2. 其它方法

   1. 首先，所有的递归都能通过迭代来实现（递归就是函数栈的调用，因此使用栈可实现迭代，博主暂时有点儿不会，手动尴尬）