Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. JavaScript

JavaScript數據結構:樹

by
Read Time:5 minsLanguages:
This post is part of a series called Data Structures in JavaScript.
Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List

Chinese (Traditional) (中文(繁體)) translation by Stypstive (you can also view the original English article)

Final product imageFinal product imageFinal product image
What You'll Be Creating

樹是在 web 開發中最常用的數據結構之一。 這種說法對開發者和用戶都是正確的。 每個編寫HTML並將其加載到Web瀏覽器的Web開發人員都創建了一個樹,稱為文檔對象模型(DOM)。 相應地,每個網絡上的消費信息的人,接受信息也以DOM樹的形式。

現在,高潮來了:你正在讀的本文在瀏覽器中就是以樹的形式進行渲染的。 元素又嵌套在元素中;元素又嵌套在元素中。文字由<p>元素進行表示;<p>元素又嵌套在<body>元素中;<body>元素又嵌套在<html>元素中。

這些嵌套數據和家族數類似。 <html> 是父元素,<body>是子元素,<p>又是<body>的子元素。 如果这个比喻对你有点用的话,你将会发现在我们介绍树的时候会用到更多的类比。

在本文中,我們將會通過兩個不同的樹遍歷方式來創建一個樹:深度優先(DFS)和廣度優先(BFS)。 如果你對遍歷這個詞感到比較陌生,不妨將他想象成訪問樹中的每一個節點。) 這兩種類型的遍歷強調了與樹交互的不同方式,而且,結合這個系列的數據結構。 DFS和BFS分別用棧和隊列來訪問節點。 聽起來很酷!!!

樹(深度搜索和廣度搜索)

在計算機科學中,樹是一種用節點來模擬分層數據的數據結構。 每個樹節點都包含他本身的數據及指向其他節點的指針。

節點和指針這些術語可能對一些讀者來說比較陌生,所以讓我們用類比來進一步描述他們。 讓我們將樹與組織圖結構圖進行比較。 這個結構圖有一個頂級位置(根節點),比如CEO。 在這個節點下面還有一些其他的節點,比如副總裁(VP)。 在這個節點下面還有一些其他的節點,比如副總裁(VP)。

為了表示這種關系,我們用箭頭從CEO指向VP。 一個位置,比如CEO,是一個節點;我們創建的CEO到VP的關系是一個指針。 在我們的組織結構圖中去創建更多的關系,我們只要重復這些步驟即可---我們讓一個節點指向另一個節點。

在概念層次上,我希望節點和指針有意義。 在實際中,我們能從更科學的實例中獲取收益。 讓我們來思考DOM。 DOM有<html>元素作為其頂級位置(根節點)。 這個節點指向<head>元素和<body>元素。 這些步驟在DOM的所有節點中重復。

這種設計的一個優點是能夠嵌套節點:例如:一個<ul>元素能夠包含很多個<li>元素;此外,每個<li>元素能擁有兄弟<li>元素。 著很怪異,但是確實真實有趣! 著很怪異,但是確實真實有趣!

操作樹

由於每個樹都包含節點,其可以是來自樹的單獨構造器,我們將概述兩個構造函數的操作:NodeTree

節點

  • data存儲值。
  • parent指向節點的父節點。
  • children指向列表中的下一個節點。


  • _root指向一個樹的根節點。
  • traverseDF(callback)對樹進行DFS遍歷。
  • traverseBF(callback)對樹進行BFS遍歷。
  • contains(data, traversal)搜索樹中的節點。
  • add(data, toData, traverse)向樹中添加節點。
  • remove(child, parent)移除樹中的節點。

實現樹

現在讓我們寫下樹的代碼!

節點的屬性

在我們的實現中,我們首先定義一個叫做Node的函數,然後構造一個Tree

每一個Node實例都包含三個屬性:dataparant,和children。 第一個屬性保存與節點相關聯的數據。 第二個屬性指向一個節點。 第三個屬性指向許多子節點。

樹的屬性

現在讓我們來定義Tree的構造函數,其中包括Node構造函數的定義:

Tree包含兩行代碼。 第一行創建了一個Node的新實例;第二行讓node等於樹的根節點。

TreeNode的定義只需要幾行代碼。 但是,通過這幾行足以幫助我們模擬分層數據。 為了證明這一點,讓我們用一些示例數據去創建Tree的示例(和間接的Node)。

幸虧有parentchildren的存在,我們可以為_root添加子節點和讓這些子節點的父節點等於_root。 換一種說法,我們可以模擬分層數據的創建。

Tree的方法

接下來我們將要創建以下五種方法。


  1. traverseDF(callback)
  2. traverseBF(callback)
  3. contains(data, traversal)
  4. add(child, parent)
  5. remove(node, parent)

因為每種方法都需要我們去遍歷一個樹,所以我們首先要實現一個方法去定義不同的樹遍歷。 (遍歷樹是一種正式的方式來訪問樹的每個節點。)

1 of 5: traverseDF(callback)

這種方法以DFS這種方式遍歷樹。

traverseDF(callback)有一個參數callback。 如果對這個名字不明白,callback被假定是一個函數,將在後面被traverseDF(callback)調用。

traverseDF(callback)的函數體含有另一個叫做recurse的函數。 這個函數是一個遞歸函數! 換句話說,它是自我調用和自我終止。 使用recurse的註釋中提到的步驟,我將描述遞歸用來recurse整個樹的一般過程。

這裏是步驟:

  1. 立即使用樹的根節點作為其參數調用recurse。 此時,currentNode指向當前節點。
  2. 進入for循環並且從第一個子節點開始,每一個子節點都叠代一次currentNode函數。
  3. for循環體內,使用currentNode的子元素調用遞歸。 確切的子節點取決於當前for循環的當前叠代。
  4. currentNode不存在子節點時,我們退出for循環並callback我們在調用traverseDF(callback)期間傳遞的回調。

步驟2(自終止),3(自調用)和4(回調)重復,直到我們遍歷樹的每個節點。

遞歸是一個非常困難的話題,需要一個完整的文章來充分解釋它。 由於遞歸的解釋不是本文的重點 - 重點是實現一棵樹 - 我建議任何讀者沒有很好地掌握遞歸做以下兩件事。

首先,實驗我們當前的traverseDF(callback)實現,並嘗試一定程度上理解它是如何工作的。 第二,如果你想要我寫一篇關於遞歸的文章,那麽請在本文的評論中請求它。

以下示例演示如何使用traverseDF(callback)遍歷樹。 要遍歷樹,我將在下面的示例中創建一個。 我現在使用的方法不是理想的,但它能很好的工作。 一個更好的方法是使用add(value),我們將在第4步和第5步中實現。

現在,讓我們調用traverseDF(callback)

2 of 5: traverseBF(callback)

這個方法使用深度優先搜索去遍歷樹

深度優先搜索和廣度優先搜索之間的差別涉及樹的節點訪問的序列。 為了說明這一點,讓我們使用我們從traverseDF(callback)創建的樹。

現在,讓我們傳遞traverseBF(callback)和我們用於traverseDF(callback)的回調。

來自控制臺的日誌和我們的樹的圖顯示了關於廣度優先搜索的模式。 從根節點開始;然後行進一個深度並訪問該深度從左到右的每個節點。 重復此過程,直到沒有更多的深度要移動。

由於我們有一個廣度優先搜索的概念模型,現在讓我們實現使我們的示例工作的代碼。

我們對traverseBF(callback)的定義包含了很多邏輯。 因此,我將以可管理的步驟解釋邏輯:

  1. 創建 Queue的實例。
  2. 將調用traverseBF(callback)的節點添加到Queue的實例。
  3. 定義一個變量currentNode並且將他的值初始化為剛才添加到隊列裏的node。
  4. currentNode指向一個節點時,執行wille循環裏面的代碼。
  5. for循環去叠代currentNode的子節點。
  6. for循環體內,將每個子元素加入隊列。
  7. 獲取currentNode並將其作為callback的參數傳遞。
  8. currentNode重新分配給正從隊列中刪除的節點。
  9. 直到currentNode不在指向任何節點-也就是說樹中的每個節點都訪問過了-重復4-8步。

3 of 5: contains(callback, traversal)

讓我們定義一個方法,讓我們在樹中搜索一個特定的值。 去使用我們創建的任一種樹遍歷方法,我們已經定義了contains(callback, traversal)接收兩個參數:搜索的數據和遍歷的類型。

contains(callback, traversal)函數體內,我們用call方法去傳遞thiscallback。 第一個參數將traversal綁定到被調用的樹contains(callback,traversal);第二个参数是树种每个节点被调用的函数。

想象一下,我們要將包含奇數數據的任何節點記錄到控制臺,並使用BFS遍歷樹中的每個節點。 代碼我們可以這麽寫:

4 of 5: add(data, toData, traversal)

現在我們有了一個可以搜索樹中特定節點的方法。 現在讓我們定義一個允許我們向指定節點添加節點的方法。

add(data, toData, traversal)定義了三個參數。 第一個參數,data,用來創建一個Node的新實例。 第二個參數,toData,用來比較樹中的每個節點。 第三個參數,traversal,是這個方法中用來遍歷樹的類型。

add(data, toData, traversal)函數體內,我們聲明了三個變量。 第一個變量,child,代表初始化的Node實例。 第二個變量,parent,初始化為null;但是將來會指向匹配toData值的樹中的任意節點。 parent的重新分配發生在我們聲明的第三個變量,這就是callback

callback是一個將toData和每一個節點的data屬性做比較的函數。 如果if語句的值是true,那麽parent將被賦值給if語句中匹配比較的節點。

每個節點的toData比較發生在contains(callback, traversal)。 遍歷類型和callback必須作為contains(callback, traversal)的參數進行傳遞。

最後,如果parent不存在於樹中,我們將child推入parent.children; 同時也要將parent賦值給child的父級。 否則,將拋出錯誤。 否則,將拋出錯誤。

讓我們用add(data, toData, traversal)做個例子:

這裏是add(addData, toData, traversal)的更加復雜的例子:

5 of 5: remove(data, fromData, traversal)

為了完成Tree的實現,我們將添加一個叫做remove(data, fromData, traversal)的方法。 跟從DOM裏面移除節點類似,這個方法將移除一個節點和他的所有子級。

add(data, toData, traversal)類似,移除將遍歷樹以查找包含第二個參數的節點,現在為fromData。 如果這個節點被發現了,那麽parent將指向它。

在這時候,我們到達了第一個if語句。 如果parent不存在,將拋出錯誤。 如果parent不存在,我們使用parent.children調用findIndex()和我們要從parent節點的子節點中刪除的數據 (findIndex()是一個幫助方法,我將在下面定義。) (findIndex()是一個幫助方法,我將在下面定義。)

findIndex()裏面,以下邏輯將發生。 如果parent.children中的任意一個節點包含匹配data值的數據,那麽變量index賦值為一個整數。 如果沒有子級的數值屬性匹配data,那麽index保留他的默認值undefined。 在最後一行的findIndex()方法,我們返回一個index

我們現在去remove(data, fromData, traversal) 。 如果index的值是undefined,將會拋出錯誤。 如果index的值存在,我們用它來拼接我們想從parent的子節點中刪除的節點。同樣我們給刪除的子級賦值為childToRemove

最後,我們返回childToRemove

至此我們完成了Tree的完整實現。

至此我們完成了Tree的完整實現。 回過頭看看-我們完成了很多工作:

總結

樹的模擬分層數據。 我們的周圍有許多類似於這種類型的層次結構,如網頁和我們的家庭。 任何時候你發現自己需要結構化數據與層次結構,考慮使用樹。

关注我们的公众号
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.