js樹形遞歸代碼（js遞歸遍歷樹）

本文目錄一覽：

• 1、JS函數式編程和遞歸探索：路由樹的操作
• 2、js中平級數組和樹形結構數據相互轉換
• 3、JS樹結構數據的遍歷
• 4、Vue.js怎樣把遞歸組件構建為樹形菜單

JS函數式編程和遞歸探索：路由樹的操作

開始切入正題之前，有必要告知大家一下，這篇文章可能有一些深度，初學者可能理解會有些吃力。我會盡量把複雜問題簡單化，爭取讓每個閱讀的童鞋們都能看得懂。希望你對element-ui，vue-router，KeepAlive組件有一點了解。現在，我們開始吧。

熟悉element-ui的童鞋們都知道，ElMenuItem和ElSubMenu都需要一個index屬性，該屬性必須是唯一的。現在，我們想把路由配置直接應用於ElMenu，該如何確保index的唯一性呢？我們需要有一個生成唯一index的函數。如下是genKey函數的定義，是不是很簡單？

現在，我們創建addRouteMetaKey函數，該函數對路由樹進行遞歸遍歷，為每一個路由配置的meta屬性動態添加key字段。這個函數很簡單，屬於最基礎的遞歸使用例子，我就不做太多解釋了。

提示 ：數組的forEach方法不是純函數，因為它有副作用，所以forEach方法不能稱之為函數式編程工具。

通過addRouteMetaKey函數，我們可以把路由的meta.key作為index的值了。

現在，我們想實現另一個功能，就是 基於標籤頁的路由組件緩存控制 。使用過Vuejs KeepAlive組件的童鞋們，應該多多少少都遇到一些坑吧？在我們的項目中，有一個頂部標籤頁導航，每個tab項對應一個url，以每個url對應路由的title作為tab項標題，當切換tab的時候加載緩存中的url對應的路由組件，關閉tab項，下次打開該路由url，重新掛載對應的路由組件，而不是從緩存中加載。

當路由層級不確定的時候，KeepAlive會變的難以手動控制。所以，我 劍走偏鋒，嘗試了一種簡單的解決方案 ，實踐證明： 這是非常有效的 。我的方案就是把無限層級的路由樹轉化為一維數組。通過為meta添加必要的字段，進行頁面結構個性化定製。

我們需要把每層路由配置的path轉化為全路徑，所以需要一個函數：getRouteFullPath，該函數定義如下：

getRouteFullPath函數中使用到的joinPath函數用於將多個路徑字符串拼接為1個完整的路徑，定義如下：

現在，我們把路由樹轉化為一維數組。我們定義toFlatRoutes函數，該函數使用了數組的reduce方法對路由樹進行聚合遞歸，將路由配置中的path屬性的值替換為全路徑，還順便給路由配置添加了name屬性，返回一個新的一維路由配置數組。 這是函數式編程和遞歸結合的一個例子。

以上，我們解決了KeepAlive的緩存控制問題；現在，我們又有了一個新的用戶體驗上的需求，就是我們想根據url對應的路由，自動展開該路由meta.key所屬的側邊菜單；我們通過查閱element-ui文檔得知，ElMenu有一個open方法，接收index作為參數，展開index對應的菜單。

現在的問題是，我們的路由對應的index是ElMenuItem的，而路由樹已經被我們轉化為了一維數組，通過路由的matched字段是得不到我們想要的菜單index的。所以， 我們需要遍歷原始路由樹 。

如下代碼，我們定義getMenuKey函數，該函數接收的參數為route對象。如果路由存在，我們進行查找。首先進行簡單查找，如果找到一個菜單menu，則返回該菜單的meta.key；如果簡單查找無果，則對路由樹進行遞歸查找； 這是函數式編程和遞歸結合的另一個例子。

現在，我們大功告成了；以上就是本節的知識點，童鞋們理解了嗎？只要我們熟悉遞歸的使用，其實操作樹很簡單。如果大家還有不懂的，可以評論區問我。感謝閱讀！

js中平級數組和樹形結構數據相互轉換

在實際的工作和業務需求中，我們經常會碰到樹形數據結構，比如公司組織架構、組織層級、省市縣或者事物的分類等等數據。那麼在JavaScript中如何將數組轉為樹形結構和樹形結構轉為數組，本文就詳細的來探究一下。

先來看看給出了一組怎樣的數據，轉換為怎樣的樹形結構。

後台接口返回或者面試官給你的數據：

期望的處理後的數據：

如果後台給了一個這樣的數據說讓前端自己去轉換為樹形結構或者面試官給你一組這樣的數據讓你手寫一個轉換方法，你會怎麼處理？

1、遞歸實現

2、Map對象實現

3、filter實現

這種方法很有意思，可能大多數人想不到，也是從大佬處學到的(讀書人的是怎麼能叫抄呢，應該叫“竊”）。

1、reduce取樹行數據的所有子集

2、遞歸實現

3、廣度優先遍曆法

JS樹結構數據的遍歷

title: JS樹結構數據的遍歷

date: 2022-04-14

description: 針對項目中出現樹形結構數據的時候，我們怎樣去操作他

項目中我們會經常出現對樹形結構的遍歷、查找和轉換的場景，比如說DOM樹、族譜、社會機構、組織架構、權限、菜單、省市區、路由、標籤等等。那針對這些場景和數據，我們又如何去遍歷和操作，有什麼方式或者技巧可以簡化我們的實現思路。下面我們將針對常規出現的場景去總結一下我們的遍歷方式

樹的特點

1、每個節點都只有有限個子節點或無子節點；

2、沒有父節點的節點稱為根節點；

3、每一個非根節點有且只有一個父節點；

4、除了根節點外，每個子節點可以分為多個不相交的子樹；

5、樹裡面沒有環路

下面的圖片表示一顆樹

在下面的JS中我們由多棵樹組成我們的數據

在這數據中我們如何評判數據是否為葉節點（也就是最後一級），我們每個節點都會存在children屬性，如果不存在children屬性或者children不是一個數組或者children為數組且長度為0我們則認為他是一個葉節點

我們針對樹結構的操作離不開遍歷，遍歷的話又分為廣度優先遍歷、深度優先遍歷。其中深度優先遍歷可以通過遞歸和循環的方式實現，而廣度優先遍歷的話是非遞歸的

從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。即訪問樹結構的第n+1層前必須先訪問完第n層。

簡單的說，BFS是從根節點開始，沿着樹的寬度遍歷樹的節點。如果所有節點均被訪問，則算法中止。

所以我們的實現思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重複執行以下步驟直到隊列為空：

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

深度優先搜索算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜索樹或圖的算法。這個算法會儘可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止

1、先序遍歷

訪問子樹的時候，先訪問根再訪問根的子樹

2、後序遍歷

訪問子樹的時候，先訪問子樹再訪問根

1、先序遍歷

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

2、後序遍歷

後序遍歷就略微複雜一點，我們需要不斷將子樹擴展到根節點前面去，執行列表遍歷，並且通過一個臨時對象維護一個id列表，當遍歷到某個節點如果它沒有子節點或者它本身已經存在於我們的臨時id列表，則執行訪問操作，否則繼續擴展子節點到當前節點前面

對於樹結構的遍歷操作，其實遞歸是最基礎，也是最容易理解的。遞歸本身就是循環的思想，所以可以用循環來改寫遞歸,以上的方式在項目中已經廊括了大部分的場景了，我們在日常開發中可以根據場景或者需要去選擇我們的遍歷方式，或者基於此對他進行調整和優化，至於每種方式的空間複雜度和時間複雜度我們在這個地方就不去嘗試了，各位感興趣可以自己去驗證。

廣度優先搜索

樹的遍歷

深度優先搜索

圖文詳解兩種算法：深度優先遍歷（DFS）和廣度優先遍歷（BFS）

二叉樹遍歷（前序，後序，中序，層次）遞歸與迭代實現JavaScript

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

Vue.js怎樣把遞歸組件構建為樹形菜單

Vue.js 遞歸組件實現樹形菜單

main.js 作為入口：

import Vue from ‘vue’import main from ‘./components/main.vue’ new Vue({ el: ‘#app’, render: h = h(main)})

它引入了一個組件 main.vue：

template div my-tree :data=”theData” :name=”menuName” :loading=”loading” @getSubMenu=”getSubMenu”/my-tree /div/template scriptconst myData = [ { id: ‘1’, menuName: ‘基礎管理’, menuCode: ’10’ }, { id: ‘2’, menuName: ‘商品管理’, menuCode: ” }, { id: ‘3’, menuName: ‘訂單管理’, menuCode: ’30’, children: [ { menuName: ‘訂單列表’, menuCode: ’31’ }, { menuName: ‘退貨列表’, menuCode: ’32’, children: [] } ] }, { id: ‘4’, menuName: ‘商家管理’, menuCode: ”, children: [] }]; const subMenuData1 = { parentId: ‘1’, children: [ { menuName: ‘用戶管理’, menuCode: ’11’ }, { id: ’12’, menuName: ‘角色管理’, menuCode: ’12’, children: [ { menuName: ‘管理員’, menuCode: ‘121’ }, { menuName: ‘CEO’, menuCode: ‘122’ }, { menuName: ‘CFO’, menuCode: ‘123’ }, { menuName: ‘COO’, menuCode: ‘124’ }, { menuName: ‘普通人’, menuCode: ‘124’ } ] }, { menuName: ‘權限管理’, menuCode: ’13’ } ]}; const subMenuData2 = { parentId: ‘2’, children: [ { menuName: ‘商品一’, menuCode: ’21’ }, { id: ’22’, menuName: ‘商品二’, menuCode: ’22’, children: [ { menuName: ‘子類商品1’, menuCode: ‘221’ }, { menuName: ‘子類商品2’, menuCode: ‘222’ } ] } ]}; import myTree from ‘./common/treeMenu.vue’export default { components: { myTree }, data () { return { theData: myData, menuName: ‘menuName’, // 顯示菜單名稱的屬性 loading: false } }, methods: { getSubMenu (menuItem, callback) { this.loading = true; if (menuItem.id === subMenuData1.parentId) { this.loading = false; menuItem.children = subMenuData1.children; callback(menuItem.children); } setTimeout(() = { if (menuItem.id === subMenuData2.parentId) { this.loading = false; menuItem.children = subMenuData2.children; callback(menuItem.children); } }, 2000); } }}/script

subMenuData1, subMenuData2 存放子菜單數據，可以從服務器獲取，以實現動態加載。

該文件引入了樹形組件 treeMenu.vue：

template ul class=”tree-menu” li v-for=”(item, index) in data” span @click=”toggle(item, index)” i :class=”[‘icon’, item.children item.children.length ? folderIconList[index] : ‘file-text’, loading ? loadingIconList[index] : ”]”/i {{ item[name] || item.menuName }} /span tree-menu v-if=”scope[index]” :data=”item.children”/tree-menu /li /ul/template scriptexport default { name: ‘treeMenu’, props: { data: Array, name: String, loading: Boolean }, data () { return { folderIconList: [], loadingIconList: [], scope: {} } }, created () { this.data.forEach((item, index) = { if (item.children item.children.length) { this.folderIconList[index] = ‘folder’; } }); }, methods: { doTask (index) { this.$set(this.scope, index, !this.scope[index]); this.folderIconList[index] = this.scope[index] ? ‘folder-open’ : ‘folder’; }, toggle (item, index) { this.loadingIconList = []; if (item.children item.children.length) { this.doTask(index); } else { this.loadingIconList[index] = ‘loading’; this.$emit(‘getSubMenu’, item, (subMenuList) = { if (subMenuList subMenuList.length) { this.doTask(index); } }); } } }}/script style scoped.tree-menu { list-style: none;}.tree-menu li { line-height: 2;}.tree-menu li span { cursor: default;}.icon { display: inline-block; width: 15px; height: 15px; background-repeat: no-repeat; vertical-align: -2px;}.icon.folder { background-image: url(/src/assets/folder.png);}.icon.folder-open { background-image: url(/src/assets/folder-open.png);}.icon.file-text { background-image: url(/src/assets/file-text.png);}.icon.loading { background-image: url(/src/assets/loading.gif); background-size: 15px;}/style