数据结构转换，笔试题系列
今天分享一道面试手写笔试题，主要是考察数据结构处理，以及数据引用问题
题目是下面这样的：将原数据根据pid进行转换成一个tree结构,也就是将pid归类到id相等的分组中去,当前的pid与id不会相等
// 原数据
var sourceData = [
{ id: 0, pid: 1, order: 1 },
{ id: 1, pid: 0, order: 1 },
{ id: 2, pid: 0, order: 1 },
{ id: 3, pid: 2, order: 1 },
{ id: 4, pid: 2, order: 1 },
{ id: 5, pid: 2, order: 1 },
{ id: 5, pid: 3, order: 1 },
{ id: 6, pid: 5, order: 1 },
{ id: 7, pid: 1, order: 2 }
];
转换成以下数据结构
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 2,
"pid": 0,
"order": 1,
"child": [
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
}
]
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 2,
"pid": 0,
"order": 1,
"child": [
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
}
]
},
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
},
...
]
大致思路就是双层循环，后面的pid是否等于前面的id,如果相等就添加一个child属性，并将数据添加到 child
const transformTree = (source) => {
// 拷贝一份新的数据
let newData = JSON.parse(JSON.stringify(source));
for (let i = 0; i < newData.length; i++) {
const item = newData[i];
// 每一项添加一个child属性
item.child = [];
for (let j = i + 1; j < newData.length; j++) {
// 0-1，0-2，0-3,...,1-1，1-2...这样依次比较
if (item.id === newData[j].pid) {
item.child.push(newData[j]);
}
}
}
return newData
}
console.log(JSON.stringify(transformTree(sourceData), null, 2));
console.log(sourceData);
最后的结果就是我们前面看到的，但是我们会发现其实数据结构里面会是这样的
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
...
]
在id=0的根数据上，我们看到添加进去了child,child里面又有与id相同的pid数据，所以你看到了一个树的结构。但是我们看到之前并没有用递归的方式。这就是很奇怪了？我们仔细思考下
当i=0时，然后依次循环当前i=0会动态新增一个child属性, arr[0].child = []
当j=1时，arr[1].child = [],此时arr[1].pid === arr[0].id，所以就会把当前的arr[1]添加到arr[0].child中
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
}
}
...
]
当i=1时，此时也会动态添加一个child属性， arr[1] = [], 此时你会发现，会变成下面这样
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": []
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": []
}
...
]
当j=6时，arr[6].pid===arr[1].id,然后你arr[1].child.push(arr[6])
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
],
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
}
...
]
本质上这两个数据就是同一份引用
我们也看到我们对原数据进行一份深拷贝，这样处理就不会影响原数据，正常情况我们处理原数据，涉及到新值删除操作时，最好不要在原有数据上进行操作。
关于数据引赋值问题可以分析下面的一个问题
const obj = { c: 1 };
const obj2 = obj;
obj2.c = '22';
console.log(obj.c, obj2.c)
结果就是22,22
但是下面这样的呢
var name = 'Maic';
var cnane = name;
cname = 'Web技术学苑';
console.log(name, cname);
我们发现结果就是Maic, Web技术学苑，与上面正好不太一样
我们继续看下下面这段代码
const obj3 = { name: 'Maic', info: { name: 'Web技术学苑' } }
const obj4 = { ...obj3 };
obj4.name = 'Tom';
obj4.info.name = 'infoQ';
console.log(obj3, obj4)
最后的结果：
obj3：{ name: 'Maic', info: { name: 'infoQ' } }
obj4：{ name: 'Tom', info: { name: 'infoQ' } }
这涉及一个问题就是基础数据类型与引用类型赋值的问题，对象与基础数据类型赋值是值拷贝，而扩展运算符是浅拷贝，当值拷贝一个引用数据类型，新的值修改会影响原有的值，当浅拷贝一份数据时，如果对象key的值是基础数据类型，那么新值修改不会影响原值，如果是引用数据类型，那么新值会影响原有的值
最后，看下另外一种比较简单的写法，不过功能是一样的
const transformTree3 = (source) => {
const arr = JSON.parse(JSON.stringify(source));
for (let i = 0; i < arr.length; i++) {
const item = arr[i];
// 从剩下的元素中过滤获取id与pid的数据归类
item.child = arr.slice(i + 1, arr.length).filter(v => v.pid === item.id);
}
return arr;
}
console.log(JSON.stringify(transformTree3(sourceData), null, 2));
总结
- 根据一维数组结构转换成树结构，主要考察引用数据类型赋值问题，我们也是利用引用数据类型巧妙的构建树结构
- 引用数据类型与基础数据类型赋值拷贝问题，如果是基础数据类型，新值赋值改变不会影响原有的值，如果是引用数据类型，新值修改会影响原有的值，如果利用
es6扩展运算符来浅拷贝原数据时，如果原数据key对应的值时引用数据类型，那么修改新值会影响原有的值，如果是基础数据类型，那么修改新值不会影响原有的值 - 本文示例code example[1]
参考资料
[1]code example： https://github.com/maicFir/lessonNote/tree/master/面试题/04-数据结构转换
最后，看完觉得有收获的，点个赞，在看，转发，收藏等于学会，欢迎关注Web技术学苑，好好学习，天天向上！