經(jīng)常有同學(xué)問(wèn)樹(shù)結(jié)構(gòu)的相關(guān)操作，也寫(xiě)了很多次，在這里總結(jié)一下JS樹(shù)形結(jié)構(gòu)一些操作的實(shí)現(xiàn)思路，并給出了簡(jiǎn)潔易懂的代碼實(shí)現(xiàn)。

本文內(nèi)容結(jié)構(gòu)大概如下：

一、遍歷樹(shù)結(jié)構(gòu)

1. 樹(shù)結(jié)構(gòu)介紹

JS中樹(shù)結(jié)構(gòu)一般是類(lèi)似于這樣的結(jié)構(gòu)：

let

為了更通用，可以用存儲(chǔ)了樹(shù)根節(jié)點(diǎn)的列表表示一個(gè)樹(shù)形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的children屬性（如果有）是一顆子樹(shù)，如果沒(méi)有children屬性或者children長(zhǎng)度為0，則表示該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。

2. 樹(shù)結(jié)構(gòu)遍歷方法介紹

樹(shù)結(jié)構(gòu)的常用場(chǎng)景之一就是遍歷，而遍歷又分為廣度優(yōu)先遍歷、深度優(yōu)先遍歷。其中深度優(yōu)先遍歷是可遞歸的，而廣度優(yōu)先遍歷是非遞歸的，通常用循環(huán)來(lái)實(shí)現(xiàn)。深度優(yōu)先遍歷又分為先序遍歷、后序遍歷，二叉樹(shù)還有中序遍歷，實(shí)現(xiàn)方法可以是遞歸，也可以是循環(huán)。

廣度優(yōu)先和深度優(yōu)先的概念很簡(jiǎn)單，區(qū)別如下：

• 深度優(yōu)先，訪問(wèn)完一顆子樹(shù)再去訪問(wèn)后面的子樹(shù)，而訪問(wèn)子樹(shù)的時(shí)候，先訪問(wèn)根再訪問(wèn)根的子樹(shù)，稱(chēng)為先序遍歷；先訪問(wèn)子樹(shù)再訪問(wèn)根，稱(chēng)為后序遍歷。
• 廣度優(yōu)先，即訪問(wèn)樹(shù)結(jié)構(gòu)的第n+1層前必須先訪問(wèn)完第n層

3. 廣度優(yōu)先遍歷的實(shí)現(xiàn)

廣度優(yōu)先的思路是，維護(hù)一個(gè)隊(duì)列，隊(duì)列的初始值為樹(shù)結(jié)構(gòu)根節(jié)點(diǎn)組成的列表，重復(fù)執(zhí)行以下步驟直到隊(duì)列為空：

• 取出隊(duì)列中的第一個(gè)元素，進(jìn)行訪問(wèn)相關(guān)操作，然后將其后代元素（如果有）全部追加到隊(duì)列最后。

下面是代碼實(shí)現(xiàn)，類(lèi)似于數(shù)組的forEach遍歷，我們將數(shù)組的訪問(wèn)操作交給調(diào)用者自定義，即一個(gè)回調(diào)函數(shù)：

// 廣度優(yōu)先

很簡(jiǎn)單吧，~,~

用上述數(shù)據(jù)測(cè)試一下看看：

treeForeach

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

>

4. 深度優(yōu)先遍歷的遞歸實(shí)現(xiàn)

先序遍歷，三五行代碼，太簡(jiǎn)單，不過(guò)多描述了：

function

后序遍歷，與先序遍歷思想一致，代碼也及其相似，只不過(guò)調(diào)換一下節(jié)點(diǎn)遍歷和子樹(shù)遍歷的順序：

function

測(cè)試：

treeForeach

輸出：

// 先序遍歷

5. 深度優(yōu)先循環(huán)實(shí)現(xiàn)

先序遍歷與廣度優(yōu)先循環(huán)實(shí)現(xiàn)類(lèi)似，要維護(hù)一個(gè)隊(duì)列，不同的是子節(jié)點(diǎn)不追加到隊(duì)列最后，而是加到隊(duì)列最前面：

function

后序遍歷就略微復(fù)雜一點(diǎn)，我們需要不斷將子樹(shù)擴(kuò)展到根節(jié)點(diǎn)前面去，（艱難地）執(zhí)行列表遍歷，遍歷到某個(gè)節(jié)點(diǎn)如果它沒(méi)有子節(jié)點(diǎn)或者它的子節(jié)點(diǎn)已經(jīng)擴(kuò)展到它前面了，則執(zhí)行訪問(wèn)操作，否則擴(kuò)展子節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)前面：

function

二、列表和樹(shù)結(jié)構(gòu)相互轉(zhuǎn)換

1. 列表轉(zhuǎn)為樹(shù)

列表結(jié)構(gòu)通常是在節(jié)點(diǎn)信息中給定了父級(jí)元素的id，然后通過(guò)這個(gè)依賴(lài)關(guān)系將列表轉(zhuǎn)換為樹(shù)形結(jié)構(gòu)，列表結(jié)構(gòu)是類(lèi)似于：

let

列表結(jié)構(gòu)轉(zhuǎn)為樹(shù)結(jié)構(gòu)，就是把所有非根節(jié)點(diǎn)放到對(duì)應(yīng)父節(jié)點(diǎn)的chilren數(shù)組中，然后把根節(jié)點(diǎn)提取出來(lái)：

function

這里首先通過(guò)info建立了id=>node的映射，因?yàn)閷?duì)象取值的時(shí)間復(fù)雜度是O(1)，這樣在接下來(lái)的找尋父元素就不需要再去遍歷一次list了，因?yàn)楸闅v尋找父元素時(shí)間復(fù)雜度是O(n)，并且是在循環(huán)中遍歷，則總體時(shí)間復(fù)雜度會(huì)變成O(n^2)，而上述實(shí)現(xiàn)的總體復(fù)雜度是O(n)。

2. 樹(shù)結(jié)構(gòu)轉(zhuǎn)列表結(jié)構(gòu)

有了遍歷樹(shù)結(jié)構(gòu)的經(jīng)驗(yàn)，樹(shù)結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)就很簡(jiǎn)單了。不過(guò)有時(shí)候，我們希望轉(zhuǎn)出來(lái)的列表按照目錄展示一樣的順序放到一個(gè)列表里的，并且包含層級(jí)信息。使用先序遍歷將樹(shù)結(jié)構(gòu)轉(zhuǎn)為列表結(jié)構(gòu)是合適的，直接上代碼:

//遞歸實(shí)現(xiàn)

三、樹(shù)結(jié)構(gòu)篩選

樹(shù)結(jié)構(gòu)過(guò)濾即保留某些符合條件的節(jié)點(diǎn)，剪裁掉其它節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)是否保留在過(guò)濾后的樹(shù)結(jié)構(gòu)中，取決于它以及后代節(jié)點(diǎn)中是否有符合條件的節(jié)點(diǎn)。可以傳入一個(gè)函數(shù)描述符合條件的節(jié)點(diǎn):

function

四、樹(shù)結(jié)構(gòu)查找

1. 查找節(jié)點(diǎn)

查找節(jié)點(diǎn)其實(shí)就是一個(gè)遍歷的過(guò)程，遍歷到滿(mǎn)足條件的節(jié)點(diǎn)則返回，遍歷完成未找到則返回null。類(lèi)似數(shù)組的find方法，傳入一個(gè)函數(shù)用于判斷節(jié)點(diǎn)是否符合條件，代碼如下：

function

2. 查找節(jié)點(diǎn)路徑

略微復(fù)雜一點(diǎn)，因?yàn)椴恢婪蠗l件的節(jié)點(diǎn)在哪個(gè)子樹(shù)，要用到回溯法的思想。查找路徑要使用先序遍歷，維護(hù)一個(gè)隊(duì)列存儲(chǔ)路徑上每個(gè)節(jié)點(diǎn)的id，假設(shè)節(jié)點(diǎn)就在當(dāng)前分支，如果當(dāng)前分支查不到，則回溯。

function

用上面的樹(shù)結(jié)構(gòu)測(cè)試：

let

輸出：

[

3. 查找多條節(jié)點(diǎn)路徑

思路與查找節(jié)點(diǎn)路徑相似，不過(guò)代碼卻更加簡(jiǎn)單：

function

五、結(jié)語(yǔ)

對(duì)于樹(shù)結(jié)構(gòu)的操作，其實(shí)遞歸是最基礎(chǔ)，也是最容易理解的。遞歸本身就是循環(huán)的思想，所以可以用循環(huán)來(lái)改寫(xiě)遞歸。熟練掌握了樹(shù)結(jié)構(gòu)的查找、遍歷，應(yīng)對(duì)日常需求應(yīng)該是綽綽有余啦。

本文提及的樹(shù)結(jié)構(gòu)操作函數(shù)，我已經(jīng)將通用的版本發(fā)布到npm，如有需要，可以直接在項(xiàng)目中下載使用

作者：MuMa

總結(jié)

以上是生活随笔為你收集整理的js用递归遍历多维数组_JavaScript树结构操作:查找、遍历、筛选、树结构和列表结构相互转换...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。