JS数据转换
笔试题
假设有这样一组数据,将其转换成树形结构的形式
[{ parent: null, id: 1, name: '北京' },
{ parent: 1, id: 11, name: '朝阳' },
{ parent: 11, id: 111, name: '朝阳1号' },
{ parent: 1, id: 12, name: '海淀' },
{ parent: 12, id: 121, name: '海淀1号' },
{ parent: null, id: 2, name: '上海' },
{ parent: 2, id: 21, name: '浦东' },
{ parent: 21, id: 211, name: '浦东1号' },
{ parent: 2, id: 22, name: '虹口' },
{ parent: 22, id: 221, name: '虹口1号'}]
输出结果:
[
{
"parent": null,
"id": 1,
"name": "北京",
"children": [
{
"parent": 1,
"id": 11,
"name": "朝阳",
"children": [
{
"parent": 11,
"id": 111,
"name": "朝阳1号"
}
]
},
{
"parent": 1,
"id": 12,
"name": "海淀",
"children": [
{
"parent": 12,
"id": 121,
"name": "海淀1号"
}
]
}
]
},
{
"parent": null,
"id": 2,
"name": "上海",
"children": [
{
"parent": 2,
"id": 21,
"name": "浦东",
"children": [
{
"parent": 21,
"id": 211,
"name": "浦东1号"
}
]
},
{
"parent": 2,
"id": 22,
"name": "虹口",
"children": [
{
"parent": 22,
"id": 221,
"name": "虹口1号"
}
]
}
]
}
]
方法一
思路:在不是根节点的情况下,当前对象通过遍历每一个除自身外的所有对象进行比较,
如果其parent与数组里面的某一个item的id匹配,即说明找到其(value的)父节点
//封装函数
function transFunc(item) {
let tree = [],
current;
//遍历数组里面的每一条数据
item.forEach((value,index)=>{
//根据parent属性,判断是否为根节点
if (value.parent==null) {
//找到根节点,保存根节点
tree.push(value)
}
//非根节点情况下,寻找它的父节点或者节点
else{
/*
思路:在不是根节点的情况下,当前对象通过遍历每一个除自身外的所有对象进行比较,
如果其parent与数组里面的某一个item的id匹配,即说明找到其(value的)父节点
*/
for (let i = 0; i < item.length-1; i++) {
//除自身以外的对象
if(index!==i){
if (item[i].id===value.parent) {
//找到父节点,将当前对象赋值到current
current = item[i];
current.children?current.children.push(value):(current.children=[value])
}
}
}=
}
})
return tree
}
var items = [{ parent: null, id: 1, name: '北京' },
{ parent: 1, id: 11, name: '朝阳' },
{ parent: 11, id: 111, name: '朝阳1号' },
{ parent: 1, id: 12, name: '海淀' },
{ parent: 12, id: 121, name: '海淀1号' },
{ parent: null, id: 2, name: '上海' },
{ parent: 2, id: 21, name: '浦东' },
{ parent: 21, id: 211, name: '浦东1号' },
{ parent: 2, id: 22, name: '虹口' },
{ parent: 22, id: 221, name: '虹口1号'}]
console.log(JSON.stringify(transFunc(items),null,2))
写这道题时,这个方法真是让人头大,最后的current我明明没有给它添加到tree,只返回tree,但是最终结果还是能实现,惊喜又蛋疼
方法二
这个方法引用自:
function arrToTree(arr, pid = null) {
const res = [];
arr.forEach(item => {
if (item.pid === pid) {
// 这样每次都需要遍历整个数组,因此时间复杂度为 n*n
// const children = arrToTree(arr, item.id)
// 往下递归时,每次数组的大小都在减小,每次都筛选掉父代元素,最终的时间复杂度为 n*logn
const children = arrToTree(arr.filter(v => v.pid !== pid), item.id);
if (children.length) {
res.push({ ...item, children })
} else {
res.push({ ...item })
}
}
});
return res;
}