開發(fā)樹形組件時(shí)，需要樹結(jié)構(gòu)的數(shù)據(jù)來填充集畅，如果此時(shí)服務(wù)器返回的是列表近弟，那就需要我們自己來轉(zhuǎn)換成樹祷愉。本篇介紹了兩種轉(zhuǎn)換方法赦颇，供大家參考。
示例數(shù)據(jù)
var list=[
{id: 1, name: 'child1', parentId: 0},
{id: 2, name: 'child2', parentId: 0},
{id: 6, name: 'child2_1', parentId: 2},
{id: 0, name: 'root', parentId: null},
{id: 5, name: 'child1_2', parentId: 1},
{id: 4, name: 'child1_1', parentId: 1},
{id: 3, name: 'child3', parentId: 0},
{id: 7, name: 'child3_1', parentId: 3}
]
示例數(shù)據(jù)是一棵樹的所有節(jié)點(diǎn)平鋪成的列表泥从，可以看到這棵樹一共有3層，父子節(jié)點(diǎn)的關(guān)系通過parentId來建立躯嫉。
嵌套循環(huán)法
這個(gè)方法使用了兩層for循環(huán)杨拐，兩層循環(huán)均遍歷整個(gè)數(shù)組，在第二層循環(huán)中確定節(jié)點(diǎn)之間的父子關(guān)系帆阳。如果節(jié)點(diǎn)的parentId和另一個(gè)節(jié)點(diǎn)的id相等，則這兩個(gè)節(jié)點(diǎn)是父子關(guān)系蜒谤，并把子節(jié)點(diǎn)添加到父節(jié)點(diǎn)的children屬性指向的數(shù)組中至扰。這個(gè)過程跟冒泡排序類似，把所有節(jié)點(diǎn)之間的關(guān)系都確認(rèn)了一遍
由于節(jié)點(diǎn)都是引用類型阶祭，只要每一個(gè)節(jié)點(diǎn)找到父節(jié)點(diǎn)绷杜，樹就會(huì)自動(dòng)形成鞭盟，不需要額外查找孫節(jié)點(diǎn)瑰剃，重孫乃至更深層的節(jié)點(diǎn)。
最后找到parentId為null的節(jié)點(diǎn)作為root節(jié)點(diǎn)培他，提取出來，得到我們想要的樹。
function transform(list){
var tree=[];
for(var i=0;i<list.length;i++){
for(var j=i;j<list.length;j++){
if(list[j].parentId===list[i].id){
if(list[i].children===undefined){
list[i].children=[];
}
list[i].children.push(list[j]);
}
else if(list[j].id===list[i].parentId){
if(list[j].children===undefined){
list[j].children=[];
}
list[j].children.push(list[i]);
}
}
if(list[i].parentId===null){
tree.push(list[i]);
}
}
return tree;
}
這個(gè)算法的時(shí)間復(fù)雜度是途蒋，節(jié)點(diǎn)數(shù)量較多時(shí)速度會(huì)比較慢。
建索引法
建索引法的核心是把父節(jié)點(diǎn)相同的子節(jié)點(diǎn)歸類懊烤，并根據(jù)它們父節(jié)點(diǎn)的id建立索引宽堆。實(shí)際上就是建立一個(gè)字典表，父節(jié)點(diǎn)id作為key畜隶，子節(jié)點(diǎn)組成的數(shù)組作為值。
{
"0":[
{id: 1, name: 'child1', parentId: 0},
{id: 2, name: 'child2', parentId: 0},
{id: 3, name: 'child3', parentId: 0}
],
"1":[
"0": {id: 5, name: "child1_2", parentId: 1}
"1": {id: 4, name: "child1_1", parentId: 1}
],
"2":[
{id: 2, name: 'child2', parentId: 0}
],
"3":[
{id: 7, name: 'child3_1', parentId: 3}
],
"null":[
{id: 0, name: 'root', parentId: null}
]
}
如果把第一個(gè)方法運(yùn)行過一遍的話浸遗，就可以看出結(jié)果已經(jīng)非常明顯了箱亿。通過索引快速找到children數(shù)組，賦值給對(duì)應(yīng)的父節(jié)點(diǎn)的children屬性届惋，最后返回parentId為null的節(jié)點(diǎn)，即為我們需要的樹郑藏。
和上一個(gè)方法一樣，運(yùn)用到了引用類型
function transform(list){
const group={};
list.forEach((item)=>{
const parentId=item.parentId;
if(!group.hasOwnProperty(parentId)){
group[parentId]=[];
}
group[parentId].push(item);
});
list.forEach(function(item){
var id=item.id;
if(group.hasOwnProperty(id)){
item.children=group;
}
})
return group["null"];
}
經(jīng)過兩輪循環(huán)就完成了由列表到樹的轉(zhuǎn)換译秦，時(shí)間復(fù)雜度為筑悴，效率較前一種方法高出不少。
