我們知道嘁锯，在前端開(kāi)發(fā)中宪祥，并不是每次 API 請(qǐng)求都會(huì)返回給我們想要的數(shù)據(jù)。比如下面這一段數(shù)據(jù)：
{
"city": [
{ "id": 12, "parent_id": 1, "name": "朝陽(yáng)區(qū)" },
{ "id": 241, "parent_id": 24, "name": "田林街道" },
{ "id": 31, "parent_id": 3, "name": "廣州市" },
{ "id": 13, "parent_id": 1, "name": "昌平區(qū)" },
{ "id": 2421, "parent_id": 242, "name": "上杭页耍科技綠洲" },
{ "id": 21, "parent_id": 2, "name": "靜安區(qū)" },
{ "id": 242, "parent_id": 24, "name": "漕河涇街道" },
{ "id": 22, "parent_id": 2, "name": "黃浦區(qū)" },
{ "id": 11, "parent_id": 1, "name": "順義區(qū)" },
{ "id": 2, "parent_id": 0, "name": "上海市" },
{ "id": 24, "parent_id": 2, "name": "徐匯區(qū)" },
{ "id": 1, "parent_id": 0, "name": "北京市" },
{ "id": 2422, "parent_id": 242, "name": "漕河涇開(kāi)發(fā)區(qū)" },
{ "id": 32, "parent_id": 3, "name": "深圳市" },
{ "id": 33, "parent_id": 3, "name": "東莞市" },
{ "id": 3, "parent_id": 0, "name": "廣東省" }
]
}
在這段數(shù)據(jù)中蝗羊，省，市仁锯，區(qū)耀找，甚至街道這些有明顯層級(jí)關(guān)系的都作為同級(jí)數(shù)據(jù)排列，這種結(jié)構(gòu)就是典型的對(duì)前端很不友好的例子业崖。一般情況下野芒，類(lèi)似這種數(shù)據(jù)，我們需要將其轉(zhuǎn)換為樹(shù)形結(jié)構(gòu)才可以正常使用双炕。
如果恰好你司的后端大佬愿意修改成你想要的結(jié)構(gòu)狞悲，那恭喜你。但實(shí)際情況是妇斤，大多數(shù)人并非這么幸運(yùn)摇锋。所謂靠天靠地不如靠自己，下面我就來(lái)介紹幾種方法站超，自己動(dòng)手修改荸恕。
方法一
我們知道，淺拷貝是拷貝對(duì)象的內(nèi)存地址死相，只要修改融求，所有引用都會(huì)同步修改。利用這個(gè)特點(diǎn)算撮，我們將子節(jié)點(diǎn)依次放入父節(jié)點(diǎn)双肤，最后將最外層父節(jié)點(diǎn)返回即可。
/**
* 數(shù)組轉(zhuǎn)樹(shù)形結(jié)構(gòu)
* @param {array} list 被轉(zhuǎn)換的數(shù)組
* @param {number|string} root 根節(jié)點(diǎn)（最外層節(jié)點(diǎn)）的 id
* @return array
*/
function arrayToTree(list, root) {
const result = [] // 用于存放結(jié)果
const map = {} // 用于存放 list 下的節(jié)點(diǎn)
// 1. 遍歷 list钮惠，將 list 下的所有節(jié)點(diǎn)以 id 作為索引存入 map
for (const item of list) {
map[item.id] = { ...item } // 淺拷貝
}
// 2. 再次遍歷，將根節(jié)點(diǎn)放入最外層七芭，子節(jié)點(diǎn)放入父節(jié)點(diǎn)
for (const item of list) {
// 3. 獲取節(jié)點(diǎn)的 id 和 父 id
const { id, parent_id } = item // ES6 解構(gòu)賦值
// 4. 如果是根節(jié)點(diǎn)素挽，存入 result
if (item.parent_id === root) {
result.push(map[id])
} else {
// 5. 反之，存入到父節(jié)點(diǎn)
map[parent_id].children
? map[parent_id].children.push(map[id])
: (map[parent_id].children = [map[id]])
}
}
// 將結(jié)果返回
return result
}
方法二
與方法一的原理一樣狸驳，但只遍歷一次预明。在遍歷的過(guò)程中缩赛，逐漸將子節(jié)點(diǎn)和父節(jié)點(diǎn)存入到 map。
/**
* 數(shù)組轉(zhuǎn)樹(shù)形結(jié)構(gòu)
* @param {array} list 被轉(zhuǎn)換的數(shù)組
* @param {number|string} root 根節(jié)點(diǎn)（最外層節(jié)點(diǎn)）
* @returns array
*/
function arrayToTreeV2(list, root) {
const result = [] // 用于存放結(jié)果
const map = {} // 用于存放 list 下的節(jié)點(diǎn)
// 遍歷 list
for (const item of list) {
// 1. 獲取節(jié)點(diǎn)的 id 和 父 id
const { id, parent_id } = item // ES6 解構(gòu)賦值
// 2. 將節(jié)點(diǎn)存入 map
if (!map[id]) map[id] = {}
// 3. 根據(jù) id撰糠，將節(jié)點(diǎn)與之前存入的子節(jié)點(diǎn)合并
map[id] = map[id].children
? { ...item, children: map[id].children }
: { ...item }
// 4. 如果是根節(jié)點(diǎn)酥馍，存入 result
if (parent_id === root) {
result.push(map[id])
} else {
// 5. 反之，存入父節(jié)點(diǎn)
if (!map[parent_id]) map[parent_id] = {}
if (!map[parent_id].children) map[parent_id].children = []
map[parent_id].children.push(map[id])
}
}
// 將結(jié)果返回
return result
}
方法三
方法三利用了遞歸阅酪。每次遍歷時(shí)旨袒，找到將本次遍歷的根節(jié)點(diǎn)作為父節(jié)點(diǎn)的所有子節(jié)點(diǎn)，直至找不到有子節(jié)點(diǎn)的术辐，此時(shí)砚尽，filter 返回空數(shù)組，遞歸停止辉词。
/**
* 數(shù)組轉(zhuǎn)樹(shù)形結(jié)構(gòu)
* @param {array} list 被轉(zhuǎn)換的數(shù)組
* @param {number|string} root 根節(jié)點(diǎn)（最外層節(jié)點(diǎn)）
* @returns array
*/
function arrayToTreeV3(list, root) {
return list
.filter(item => item.parent_id === root)
.map(item => ({ ...item, children: arrayToTreeV3(list, item.id) }))
}
性能對(duì)比
雖然以上三種方法都能實(shí)現(xiàn)將數(shù)組轉(zhuǎn)換為樹(shù)形結(jié)構(gòu)必孤，但我們明顯看到方法三的代碼最少，也最容易理解瑞躺。方法一和二原理一樣敷搪，但遍歷的次數(shù)不一樣。寫(xiě)法不一樣幢哨，意味著性能表現(xiàn)也不一樣赡勘。
下面我們就使用 JSBench 測(cè)試一下：
通過(guò)結(jié)果可以看出，方法一雖然使用了兩次遍歷嘱么，效率卻最高狮含。方法三由于使用了遞歸，代碼最少曼振，也便于理解几迄，但效率卻很差。
