JS樹結構操作：查找、遍歷、篩選、樹結構和列表結構相互轉換

經常有同學問樹結構的相關操作，也寫了很多次，在這里總結一下 JS 樹形結構一些操作的實現思路，并給出了簡潔易懂的代碼實現。

本文內容結構大概如下：

JS樹結構相關操作

遍歷樹結構

1. 樹結構介紹

JS中樹結構一般是類似于這樣的結構：

let?tree?=?[{id:?'1',title:?'節點1',children:?[{id:?'1-1',title:?'節點1-1'},{id:?'1-2',title:?'節點1-2'}]},{id:?'2',title:?'節點2',children:?[{id:?'2-1',title:?'節點2-1'}]}
]

為了更通用，可以用存儲了樹根節點的列表表示一個樹形結構，每個節點的children屬性（如果有）是一顆子樹，如果沒有children屬性或者children長度為0，則表示該節點為葉子節點。

2. 樹結構遍歷方法介紹

樹結構的常用場景之一就是遍歷，而遍歷又分為廣度優先遍歷、深度優先遍歷。

其中深度優先遍歷是可遞歸的，而廣度優先遍歷是非遞歸的，通常用循環來實現。深度優先遍歷又分為先序遍歷、后序遍歷，二叉樹還有中序遍歷，實現方法可以是遞歸，也可以是循環。

JS遍歷樹結構

廣度優先和深度優先的概念很簡單，區別如下：

深度優先，訪問完一顆子樹再去訪問后面的子樹，而訪問子樹的時候，先訪問根再訪問根的子樹，稱為先序遍歷；

先訪問子樹再訪問根，稱為后序遍歷。

廣度優先，即訪問樹結構的第n+1層前必須先訪問完第n層

3. 廣度優先遍歷的實現

廣度優先的思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重復執行以下步驟直到隊列為空：

取出隊列中的第一個元素，進行訪問相關操作，然后將其后代元素（如果有）全部追加到隊列最后。

下面是代碼實現，類似于數組的forEach遍歷，我們將數組的訪問操作交給調用者自定義，即一個回調函數：

//?廣度優先
function?treeForeach?(tree,?func)?{let?node,?list?=?[...tree]while?(node?=?list.shift())?{func(node)node.children?&&?list.push(...node.children)}
}

很簡單吧，~,~

用上述數據測試一下看看：

treeForeach(tree,?node?=>?{?console.log(node.title)?})

輸出，可以看到第一層所有元素都在第二層元素前輸出：

>?節點1
>?節點2
>?節點1-1
>?節點1-2
>?節點2-1

4. 深度優先遍歷的遞歸實現

先序遍歷，三五行代碼，太簡單，不過多描述了：

function?treeForeach?(tree,?func)?{tree.forEach(data?=>?{func(data)data.children?&&?treeForeach(data.children,?func)?//?遍歷子樹})
}

后序遍歷，與先序遍歷思想一致，代碼也及其相似，只不過調換一下節點遍歷和子樹遍歷的順序：

function?treeForeach?(tree,?func)?{tree.forEach(data?=>?{data.children?&&?treeForeach(data.children,?func)?//?遍歷子樹func(data)})
}

測試：

treeForeach(tree,?node?=>?{?console.log(node.title)?})

輸出：

//?先序遍歷
>?節點1
>?節點1-1
>?節點1-2
>?節點2
>?節點2-1//?后序遍歷
>?節點1-1
>?節點1-2
>?節點1
>?節點2-1
>?節點2

5. 深度優先循環實現

先序遍歷與廣度優先循環實現類似，要維護一個隊列，不同的是子節點不追加到隊列最后，而是加到隊列最前面：

function?treeForeach?(tree,?func)?{let?node,?list?=?[...tree]while?(node?=?list.shift())?{func(node)node.children?&&?list.unshift(...node.children)}
}

后序遍歷就略微復雜一點，我們需要不斷將子樹擴展到根節點前面去，（艱難地）執行列表遍歷，遍歷到某個節點如果它沒有子節點或者它的子節點已經擴展到它前面了，則執行訪問操作，否則擴展子節點到當前節點前面：

function?treeForeach?(tree,?func)?{let?node,?list?=?[...tree],?i?=??0while?(node?=?list[i])?{let?childCount?=?node.children???node.children.length?:?0if?(!childCount?||?node.children[childCount?-?1]?===?list[i?-?1])?{func(node)i++}?else?{list.splice(i,?0,?...node.children)}}
}

列表和樹結構相互轉換

1. 列表轉為樹

列表結構通常是在節點信息中給定了父級元素的id，然后通過這個依賴關系將列表轉換為樹形結構，列表結構是類似于：

let?list?=?[{id:?'1',title:?'節點1',parentId:?'',},{id:?'1-1',title:?'節點1-1',parentId:?'1'},{id:?'1-2',title:?'節點1-2',parentId:?'1'},{id:?'2',title:?'節點2',parentId:?''},{id:?'2-1',title:?'節點2-1',parentId:?'2'}
]

列表結構轉為樹結構，就是把所有非根節點放到對應父節點的chilren數組中，然后把根節點提取出來：

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的映射，因為對象取值的時間復雜度是O(1)，這樣在接下來的找尋父元素就不需要再去遍歷一次list了，因為遍歷尋找父元素時間復雜度是O(n)，并且是在循環中遍歷，則總體時間復雜度會變成O(n^2)，而上述實現的總體復雜度是O(n)。

2. 樹結構轉列表結構

有了遍歷樹結構的經驗，樹結構轉為列表結構就很簡單了。

不過有時候，我們希望轉出來的列表按照目錄展示一樣的順序放到一個列表里的，并且包含層級信息。

使用先序遍歷將樹結構轉為列表結構是合適的，直接上代碼:

//遞歸實現
function?treeToList?(tree,?result?=?[],?level?=?0)?{tree.forEach(node?=>?{result.push(node)node.level?=?level?+?1node.children?&&?treeToList(node.children,?result,?level?+?1)})return?result
}//?循環實現
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)?continuelet?list?=?result[i].children.map(node?=>?(node.level?=?result[i].level?+?1,?node))result.splice(i+1,?0,?...list)}return?result
}

樹結構篩選

樹結構過濾即保留某些符合條件的節點，剪裁掉其它節點。

一個節點是否保留在過濾后的樹結構中，取決于它以及后代節點中是否有符合條件的節點。

可以傳入一個函數描述符合條件的節點:

function?treeFilter?(tree,?func)?{//?使用map復制一下節點，避免修改到原樹return?tree.map(node?=>?({?...node?})).filter(node?=>?{node.children?=?node.children?&&?treeFilter(node.children,?func)return?func(node)?||?(node.children?&&?node.children.length)})
}

樹結構查找

1. 查找節點

查找節點其實就是一個遍歷的過程，遍歷到滿足條件的節點則返回，遍歷完成未找到則返回null。

類似數組的find方法，傳入一個函數用于判斷節點是否符合條件，代碼如下：

function?treeFind?(tree,?func)?{for?(const?data?of?tree)?{if?(func(data))?return?dataif?(data.children)?{const?res?=?treeFind(data.children,?func)if?(res)?return?res}}return?null
}

2. 查找節點路徑

略微復雜一點，因為不知道符合條件的節點在哪個子樹，要用到回溯法的思想。

查找路徑要使用先序遍歷，維護一個隊列存儲路徑上每個節點的id，假設節點就在當前分支，如果當前分支查不到，則回溯。

function?treeFindPath?(tree,?func,?path?=?[])?{if?(!tree)?return?[]for?(const?data?of?tree)?{path.push(data.id)if?(func(data))?return?pathif?(data.children)?{const?findChildren?=?treeFindPath(data.children,?func,?path)if?(findChildren.length)?return?findChildren}path.pop()}return?[]
}

用上面的樹結構測試：

let?result?=?treeFindPath(tree,?node?=>?node.id?===?'2-1')
console.log(result)

輸出：

["2","2-1"]

3. 查找多條節點路徑

思路與查找節點路徑相似，不過代碼卻更加簡單：

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
}