JavaScript樹結構深度優先算法

3403771864 發布于2022-09-19 22:06 / 327人閱讀

　　什么是樹

　　現實中樹隨處可見；在計算機世界，樹就是一種分層結構的抽象模型。

　　如下圖所示：

　　樹結構的可以用在很多情景，就如下圖公司的組織架構，用“樹”就可以表達出來，如下圖：

　　組織架構只是其中之一，比如族譜、省市等用樹的結構形式展現是完全可以。

　　樹的術語

　　樹有很多的術語，如下圖：

　　樹：n(n≥0)個節點所構成的有限集合，當n=0時，稱為空樹；

　　節點的度：節點的子樹個數，例如B節點的度就是2，A節點的度就是3；

　　樹的度：樹的所有節點中最大的度數，例如上圖中，樹的度是3；

　　葉子節點：度為0的節點，也叫葉節點；

　　子節點：如上圖；

　　兄弟節點：如上圖；

　　根節點：如上圖；

　　樹的深度：樹中所有結點中的最大層次，例如上圖中樹的深度就是3；

　　節點的層次：例如E節點的層次就是3，節點的層次就是父節點層次+1，根節點的層次為1；

　　路徑：一個節點到另一個節點的通道，例如A→H的路徑就是A D H；

　　路徑長度：一個節點到另一個節點的距離，例如A→H的路徑就是3。

　　JavaScript中的樹

　　樹結構可以作為最常見的數據結構之一，還有很多其他的結構如DOM樹、級聯選擇、樹形組件等等；

　　JavaScript沒有這樣的結構，開發我們的大腦，想到可以通過對象和數組來模擬一個樹，

　　例如下面這段代碼：

　　const tree = {
　　value: 'A',
　　children: [
　　{
　　value: 'B',
　　children: [
　　{ value: 'E', children: null },
　　{ value: 'F', children: null },
　　],
　　},
　　{
　　value: 'C',
　　children: [{ value: 'G', children: null }],
　　},
　　{
　　value: 'D',
　　children: [
　　{ value: 'H', children: null },
　　{ value: 'I', children: null },
　　],
　　},
　　],
　　}

　　廣度優先和深度優點遍歷算法

　　深度優先

　　所謂的深度優先遍歷算法，就是盡可能深的去搜索樹的分支，它的遍歷順序如下圖：

　　實現思路如下：

　　訪問根節點；

　　對根節點的children持續進行深度優先遍歷（遞歸）；

　　實現代碼如下：

　　function dfs(root) {
　　console.log(root.value)
　　root.children && root.children.forEach(dfs) // 與下面一致
　　// if (root.children) {
　　// root.children.forEach(child => {
　　// dfs(child)
　　// })
　　// }
　　}
　　dfs(tree) // 這個tree就是前面定義的那個樹
　　/* 結果
　　A
　　B
　　E
　　F
　　C
　　G
　　D
　　H
　　I
　　*/

　　上述展示我們想要的表示，思路沒什么問題。

　　廣度優先

　　所謂的廣度優先就是依次訪問離根節點近的節點，它的遍歷順序如下圖：

　　實現思路如下：

　　創建要給隊列，把根節點入隊；

　　把隊頭出隊并訪問；

　　把隊頭的children依次入隊；

　　重復執行2、3步，直到隊列為空。

　　實現代碼如下：

　　function bfs(root) {
　　// 1. 新建隊列 跟節點入隊
　　const q = [root]
　　// 4 重復執行
　　while (q.length > 0) {
　　const node = q.shift() // 2 隊頭出隊
　　console.log(node.value)
　　// 3 隊頭 children 依次入隊
　　node.children &&
　　node.children.forEach(child => {
　　q.push(child)
　　})
　　}
　　}
　　bfs(tree)
　　/* 結果
　　A
　　B
　　C
　　D
　　E
　　F
　　G
　　H
　　I
　　*/

　　上述展示我們想要的表示，算法沒什么問題。

云服務器 GPU云服務器深度優先深度優先搜索最高優先權優先算法最佳優先算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/127785.html

學習Virtual Dom筆記

摘要：通過深度優先遍歷兩棵樹，每層節點進行對比，記錄下每個節點的差異。所以可以對那棵樹也進行深度優先遍歷，遍歷的時候從步驟二生成的對象中找出當前遍歷的節點差異，然后進行操作。實現虛擬(Virtual) Dom 把一個div元素的屬性打印出來，如下： showImg(https://segmentfault.com/img/bVbnPe1?w=1239&h=336); 可以看到僅僅是第一層，...

DobbyKim 2019-08-26 13:28 評論0 收藏0
深度剖析：如何實現一個 Virtual DOM 算法

摘要：本文所實現的完整代碼存放在。這就是所謂的算法。兩個樹的完全的算法是一個時間復雜度為的問題。如果有差異的話就記錄到一個對象里面。如和的不同，會被所替代。這牽涉到兩個列表的對比算法，需要另外起一個小節來討論。作者：戴嘉華轉載請注明出處并保留原文鏈接（ https://github.com/livoras/blog/issues/13 ）和作者信息。目錄： 1 前言 2 對前端應用狀...

vvpvvp 2019-08-21 10:49 評論0 收藏0
Javascript的數據結構與算法(三)

摘要：存在好幾種方式來表示這種數據結構。下面的示意圖展示了鄰接表數據結構。在關聯矩陣中矩陣的行表示頂點列表示邊。廣度優先搜索算法和深度優先搜索算法基本上是相同的只有一點不同那就是待訪問頂點列表的數據結構。 1 樹一個樹結構包含一系列存在父子關系的節點。每個節點都有一個父節點(除了頂部的第一個節點)以及零個或多個子節點。位于樹頂部的節點叫作根節點(11)。它沒有父節點。樹中的每個元素都叫作...

MasonEast 2019-08-21 11:24 評論0 收藏0
JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS)

摘要：算法之深度優先遍歷和廣度優先遍歷背景在開發頁面的時候，我們有時候會遇到這種需求在頁面某個節點中遍歷，找到目標節點，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節點，同時理解一下深度優先遍歷和廣度優先遍歷的原理。 JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS) 背景在開發頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節點中遍歷，找到目標dom節點，...

roadtogeek 2019-08-23 16:33 評論0 收藏0