今天分享一道面试手写笔试题，主要是考察数据结构处理，以及数据引用问题
题目是下面这样的：将原数据根据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]
