一姜胖、遍歷樹結(jié)構(gòu)
1. 樹結(jié)構(gòu)介紹
JS中樹結(jié)構(gòu)一般是類似于這樣的結(jié)構(gòu)：
let tree = [
{
id: '1',
title: '節(jié)點1',
children: [
{
id: '1-1',
title: '節(jié)點1-1'
},
{
id: '1-2',
title: '節(jié)點1-2'
}
]
},
{
id: '2',
title: '節(jié)點2',
children: [
{
id: '2-1',
title: '節(jié)點2-1'
}
]
}
]
為了更通用，可以用存儲了樹根節(jié)點的列表表示一個樹形結(jié)構(gòu)怠蹂，每個節(jié)點的children屬性（如果有）是一顆子樹，如果沒有children屬性或者children長度為0，則表示該節(jié)點為葉子節(jié)點氢烘。
2. 樹結(jié)構(gòu)遍歷方法介紹
樹結(jié)構(gòu)的常用場景之一就是遍歷，而遍歷又分為廣度優(yōu)先遍歷家厌、深度優(yōu)先遍歷播玖。其中深度優(yōu)先遍歷是可遞歸的，而廣度優(yōu)先遍歷是非遞歸的饭于，通常用循環(huán)來實現(xiàn)蜀踏。深度優(yōu)先遍歷又分為先序遍歷、后序遍歷掰吕，二叉樹還有中序遍歷果覆，實現(xiàn)方法可以是遞歸，也可以是循環(huán)殖熟。
廣度優(yōu)先和深度優(yōu)先的概念很簡單局待，區(qū)別如下：
- 深度優(yōu)先，訪問完一顆子樹再去訪問后面的子樹菱属，而訪問子樹的時候钳榨，先訪問根再訪問根的子樹，稱為先序遍歷纽门；先訪問子樹再訪問根薛耻，稱為后序遍歷。
- 廣度優(yōu)先膜毁，即訪問樹結(jié)構(gòu)的第n+1層前必須先訪問完第n層
3. 廣度優(yōu)先遍歷的實現(xiàn)
廣度優(yōu)先的思路是昭卓，維護(hù)一個隊列，隊列的初始值為樹結(jié)構(gòu)根節(jié)點組成的列表瘟滨，重復(fù)執(zhí)行以下步驟直到隊列為空：
- 取出隊列中的第一個元素候醒，進(jìn)行訪問相關(guān)操作，然后將其后代元素（如果有）全部追加到隊列最后杂瘸。
下面是代碼實現(xiàn)倒淫，類似于數(shù)組的forEach遍歷，我們將數(shù)組的訪問操作交給調(diào)用者自定義败玉，即一個回調(diào)函數(shù)：
// 廣度優(yōu)先
function treeForeach (tree, func) {
let node, list = [...tree]
while (node = list.shift()) {
func(node)
node.children && list.push(...node.children)
}
}
很簡單吧敌土，用上述數(shù)據(jù)測試一下看看：
treeForeach(tree, node => { console.log(node.title) })
輸出镜硕，可以看到第一層所有元素都在第二層元素前輸出：
> 節(jié)點1
> 節(jié)點2
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點2-1
4. 深度優(yōu)先遍歷的遞歸實現(xiàn)
先序遍歷，三五行代碼返干，太簡單兴枯，不過多描述了：
function treeForeach (tree, func) {
tree.forEach(data => {
func(data)
data.children && treeForeach(data.children, func) // 遍歷子樹
})
}
后序遍歷，與先序遍歷思想一致矩欠，代碼也及其相似财剖，只不過調(diào)換一下節(jié)點遍歷和子樹遍歷的順序：
function treeForeach (tree, func) {
tree.forEach(data => {
data.children && treeForeach(data.children, func) // 遍歷子樹
func(data)
})
}
測試：
treeForeach(tree, node => { console.log(node.title) })
輸出：
// 先序遍歷
> 節(jié)點1
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點2
> 節(jié)點2-1
// 后序遍歷
> 節(jié)點1-1
> 節(jié)點1-2
> 節(jié)點1
> 節(jié)點2-1
> 節(jié)點2
5. 深度優(yōu)先循環(huán)實現(xiàn)
先序遍歷與廣度優(yōu)先循環(huán)實現(xiàn)類似，要維護(hù)一個隊列癌淮，不同的是子節(jié)點不追加到隊列最后躺坟，而是加到隊列最前面：
function treeForeach (tree, func) {
let node, list = [...tree]
while (node = list.shift()) {
func(node)
node.children && list.unshift(...node.children)
}
}
后序遍歷就略微復(fù)雜一點，我們需要不斷將子樹擴(kuò)展到根節(jié)點前面去乳蓄，（艱難地）執(zhí)行列表遍歷咪橙，遍歷到某個節(jié)點如果它沒有子節(jié)點或者它的子節(jié)點已經(jīng)擴(kuò)展到它前面了，則執(zhí)行訪問操作虚倒，否則擴(kuò)展子節(jié)點到當(dāng)前節(jié)點前面：
function treeForeach (tree, func) {
let node, list = [...tree], i = 0
while (node = list[i]) {
let childCount = node.children ? node.children.length : 0
if (!childCount || node.children[childCount - 1] === list[i - 1]) {
func(node)
i++
} else {
list.splice(i, 0, ...node.children)
}
}
}
二美侦、列表和樹結(jié)構(gòu)相互轉(zhuǎn)換
1. 列表轉(zhuǎn)為樹
列表結(jié)構(gòu)通常是在節(jié)點信息中給定了父級元素的id，然后通過這個依賴關(guān)系將列表轉(zhuǎn)換為樹形結(jié)構(gòu)魂奥，列表結(jié)構(gòu)是類似于：
let list = [
{
id: '1',
title: '節(jié)點1',
parentId: '',
},
{
id: '1-1',
title: '節(jié)點1-1',
parentId: '1'
},
{
id: '1-2',
title: '節(jié)點1-2',
parentId: '1'
},
{
id: '2',
title: '節(jié)點2',
parentId: ''
},
{
id: '2-1',
title: '節(jié)點2-1',
parentId: '2'
}
]
列表結(jié)構(gòu)轉(zhuǎn)為樹結(jié)構(gòu)音榜，就是把所有非根節(jié)點放到對應(yīng)父節(jié)點的chilren數(shù)組中，然后把根節(jié)點提取出來：
function listToTree (list) {
let info = list.reduce((map, node) => (map[node.id] = node, node.children = [], map), {})
return list.filter(node => {
info[node.parentId] && info[node.parentId].children.push(node)
return !node.parentId
})
}
這里首先通過info建立了id=>node的映射捧弃，因為對象取值的時間復(fù)雜度是O(1)赠叼，這樣在接下來的找尋父元素就不需要再去遍歷一次list了，因為遍歷尋找父元素時間復(fù)雜度是O(n)违霞，并且是在循環(huán)中遍歷嘴办，則總體時間復(fù)雜度會變成O(n^2)，而上述實現(xiàn)的總體復(fù)雜度是O(n)买鸽。
2. 樹結(jié)構(gòu)轉(zhuǎn)列表結(jié)構(gòu)
有了遍歷樹結(jié)構(gòu)的經(jīng)驗涧郊，樹結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)就很簡單了。不過有時候眼五，我們希望轉(zhuǎn)出來的列表按照目錄展示一樣的順序放到一個列表里的妆艘，并且包含層級信息。使用先序遍歷將樹結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)是合適的看幼，直接上代碼:
//遞歸實現(xiàn)
function treeToList (tree, result = [], level = 0) {
tree.forEach(node => {
result.push(node)
node.level = level + 1
node.children && treeToList(node.children, result, level + 1)
})
return result
}
// 循環(huán)實現(xiàn)
function treeToList (tree) {
let node, result = tree.map(node => (node.level = 1, node))
for (let i = 0; i < result.length; i++) {
if (!result[i].children) continue
let list = result[i].children.map(node => (node.level = result[i].level + 1, node))
result.splice(i+1, 0, ...list)
}
return result
}
三批旺、樹結(jié)構(gòu)篩選
樹結(jié)構(gòu)過濾即保留某些符合條件的節(jié)點，剪裁掉其它節(jié)點诵姜。一個節(jié)點是否保留在過濾后的樹結(jié)構(gòu)中汽煮，取決于它以及后代節(jié)點中是否有符合條件的節(jié)點。可以傳入一個函數(shù)描述符合條件的節(jié)點:
function treeFilter (tree, func) {
// 使用map復(fù)制一下節(jié)點暇赤，避免修改到原樹
return tree.map(node => ({ ...node })).filter(node => {
node.children = node.children && treeFilter(node.children, func)
return func(node) || (node.children && node.children.length)
})
}
四心例、樹結(jié)構(gòu)查找
1. 查找節(jié)點
查找節(jié)點其實就是一個遍歷的過程，遍歷到滿足條件的節(jié)點則返回鞋囊，遍歷完成未找到則返回null止后。類似數(shù)組的find方法，傳入一個函數(shù)用于判斷節(jié)點是否符合條件溜腐，代碼如下：
function treeFind (tree, func) {
for (const data of tree) {
if (func(data)) return data
if (data.children) {
const res = treeFind(data.children, func)
if (res) return res
}
}
return null
}
2. 查找節(jié)點路徑
略微復(fù)雜一點坯门，因為不知道符合條件的節(jié)點在哪個子樹，要用到回溯法的思想逗扒。查找路徑要使用先序遍歷，維護(hù)一個隊列存儲路徑上每個節(jié)點的id欠橘，假設(shè)節(jié)點就在當(dāng)前分支矩肩，如果當(dāng)前分支查不到，則回溯肃续。
function treeFindPath (tree, func, path = []) {
if (!tree) return []
for (const data of tree) {
path.push(data.id)
if (func(data)) return path
if (data.children) {
const findChildren = treeFindPath(data.children, func, path)
if (findChildren.length) return findChildren
}
path.pop()
}
return []
}
用上面的樹結(jié)構(gòu)測試：
let result = treeFindPath(tree, node => node.id === '2-1')
console.log(result)
輸出：
["2","2-1"]
3. 查找多條節(jié)點路徑
思路與查找節(jié)點路徑相似黍檩，不過代碼卻更加簡單：
function treeFindPath (tree, func, path = [], result = []) {
for (const data of tree) {
path.push(data.id)
func(data) && result.push([...path])
data.children && treeFindPath(data.children, func, path, result)
path.pop()
}
return result
}
參考文獻(xiàn)：JS樹結(jié)構(gòu)操作：查找、遍歷始锚、篩選刽酱、樹結(jié)構(gòu)和列表結(jié)構(gòu)相互轉(zhuǎn)換
對于樹結(jié)構(gòu)的操作，其實遞歸是最基礎(chǔ)瞧捌，也是最容易理解的棵里。遞歸本身就是循環(huán)的思想，所以可以用循環(huán)來改寫遞歸姐呐。
