JS数组转树（级联）
有时候，后端传递过来的数据并不是树姓结构：
[
{"id":"12","parentId":"0","text":"Man","level":"1","children":null},
{"id":"6","parentId":"12","text":"Boy","level":"2","children":null},
{"id":"7","parentId":"12","text":"Other","level":"2","children":null},
{"id":"9","parentId":"0","text":"Woman","level":"1","children":null},
{"id":"11","parentId":"9","text":"Girl","level":"2","children":null}
]这个数组的每一个子元素都有唯一的id，没有父节点时parentId为0，除0外的parentId必有id与其对应。
而我们期望的数组如下：
[
{"id":"12","parentId":"0","text":"Man","level":"1","children":
{"id":"6","parentId":"12","text":"Boy","level":"2","children":null},
{"id":"7","parentId":"12","text":"Other","level":"2","children":null}
{"id":"9","parentId":"0","text":"Woman","level":"1","children":
{"id":"11","parentId":"9","text":"Girl","level":"2","children":null}
]这里最直接的思路是先找到根节点（parentId为0），然后再将子节点放置进去。
array.push(obj)
在写代码之前，需要知道，当我们使用[].push添加一个对象时，实际上是将对象的指针加入到数组。数组和对象指向同一块内存区域，修改原对象的同时也会修改数组。
const arr = []
const obj = {a: 1, b: 2}
arr.push(obj)
obj['a'] = 111
console.log(arr) // [{a: 111, b: 2}]
console.log(obj) // {a: 111, b: 2}
那么，我们再处理数组的时候，就不必在意父子节点添加的顺序。只要修改原始对象，数组也会跟着修改。
简单版本
知道了方法，我们很容易就写出如下代码
function list_to_tree(list) {
const roots = []
for(let i = 0; i < list.length; i++){
node = list[i]
node.children = []
if(node.parentId !== '0'){
for(let j = 0; j < list.length; j++) {
if(list[j].id === node.parentId) {
list[j].children.push(node)
}else {
roots.push(node)
return roots;
很容易看懂，先遍历原始数组，将没有父节点的放入数组，有父节点的再遍历数组中找到父节点，放置上去。
这个方法虽然简单，如果数据比较大（省份城市级联），处理起来就会慢，因为里面要两次循环遍历数组来寻找父节点，复杂度为O(n²)。
改进版
在上例的两个循环中，第一个循环很难改变，必然要遍历整个数组。第二个循环用于找父节点，我们可以考虑先生成一个存储id与所在位置的 对象表 ，加快寻址速度，避免每次找父节点都需要遍历数组。
function list_to_tree(list) {
let map = {}, node, root = [], i;
for (i = 0; i < list.length; i += 1) {
map[list[i].id] = i;
// 要讲children初始化为数组
list[i].children = [];
console.log('map') // {6: 1, 7: 2, 9: 3, 11: 4, 12: 0}
for (i = 0; i < list.length; i++) {
node = list[i];
if (node.parentId !== "0") {
// 这里通过map来得到父节点的位置
list[map[node.parentId]].children.push(node);
} else {
root.push(node);
return root;
经过测试我们能够得到想要的结果。如果此时输出原始数据，会发现已经被更改,而且数据也远多于最开始。需要注意数据量比较大的时候，可能会有影响。
简单实例
下面来试验一下，我们有如下数据：
[
{"id":1,"pid":0,"name":"上海市"},
{"id":2,"pid":1,"name":"杨浦区"},
{"id":3,"pid":1,"name":"静安区"},
{"id":4,"pid":2,"name":"营口路"},
{"id":5,"pid":3,"name":"北京西路"},
{"id":6,"pid":2,"name":"长海路"},
{"id":7,"pid":3,"name":"长寿路"},
{"id":8,"pid":4,"name":"1号楼"},
{"id":9,"pid":4,"name":"2号楼"}
用我们上面的方法稍加改动:
function list_to_tree(list) {
let map = {}, node, root = [], i;
for(i = 0; i < list.length; i++) {
map[list[i].id] = i
list[i].children = []
for(i = 0; i < list.length; i++) {
const node = list[i]
if(list[i].pid !== 0) {
list[map[node.pid]].children.push(node)
}else {
root.push(node)
return root
}处理后得到:
[
{"id":1,"pid":0,"name":"上海市","children":
{"id":2,"pid":1,"name":"杨浦区","children":
{"id":4,"pid":2,"name":"黄兴路","children":
{"id":8,"pid":4,"name":"1号楼","children":[]},
{"id":9,"pid":4,"name":"2号楼","children":[]}
{"id":6,"pid":2,"name":"西藏北路","children":[]}
{"id":3,"pid":1,"name":"静安区","children":
{"id":5,"pid":3,"name":"延吉中路","children":[]},