數據結構中樹的 4 種類型解釋：屬性和應用

什麼是數據結構中的樹？

樹是一種表示分層數據的數據結構。 它具有由邊連接的節點組成的非線性結構。 在以線性數據結構執行操作的其他類型的數據結構中，複雜性隨著數據大小的增加而增加。 然而，樹數據結構提供了對非線性數據的更快訪問。 各種類型的數據結構和與之相關的算法的可用性，已經成為任務執行的一種簡單有效的方式。

與數據結構中的樹相關的一些術語是：

• 節點：節點是樹數據結構中的一個實體，它包含一個鍵或一個值以及指向其子節點的指針。
• 子節點：子節點是任何節點的後代。
• 葉節點：沒有任何子節點並且是樹中最底部的節點的節點。 它們也稱為外部節點。
• 根：它是一棵樹的最高點。
• 內部節點：至少有一個子節點的節點。
• 邊：邊是指樹中任意兩個節點之間的連接。
• 節點的高度：從節點到最深葉子的邊數。
• 節點深度：從根到節點的邊數。
• 樹的高度：根節點的高度。
• 節點度：到該節點的分支總數。
• 森林：不相交的樹木的集合。

樹的種類

1.二叉樹

二叉樹是一種樹數據結構，其中每個父節點最多有兩個子節點。 顧名思義，二進製表示兩個，因此，每個節點可以有 0、1 或 2 個節點。 二叉樹數據結構如圖 1所示。樹中的節點 1 包含兩個指針，每個指針指向一個子節點。 節點 2 也有兩個指針，每個指針指向兩個子節點。 而節點 3、5 和 6 是葉節點，因此在左右部分都有空指針。

圖 1：二叉樹的表示 ( https://www.javatpoint.com/binary-tree )。

二叉樹的屬性

• I 的每個級別的最大節點數為 2 i 。
• 圖 1中樹的高度為 3，這意味著最大節點數將為 (1+2+4+8) =15。

• 在高度 h，可能的最大節點數為 (20 + 21 + 22+….2h) = 2h+1 -1。

• 在高度 h 處，可能的最小節點數等於 h+1。

• 最小數量的節點將代表具有最大高度的樹，反之亦然。

甚至二叉樹也可以分為以下幾種樹：

• 全二叉樹：是一種特殊的二叉樹。 在這種樹數據結構中，每個父節點或內部節點要么有兩個子節點，要么沒有子節點。
• 完美二叉樹：在這種樹數據結構中，每個內部節點正好有兩個子節點，所有葉子節點都在同一層級。
• 完全二叉樹：它類似於完全二叉樹，但有一些區別。
• 每個級別都完全填滿。
• 葉節點向樹的左側傾斜。
• 最後一個葉子節點不需要有正確的兄弟節點，即完整的二叉樹不必是完整的二叉樹。
• 退化或病態樹：這些樹在父節點的左側或右側有一個子節點。
• 偏二叉樹：它是一種病態或退化的樹，其中樹由左節點或右節點支配。 因此，有兩種偏斜二叉樹，即左偏二叉樹或右偏二叉樹。
• 平衡二叉樹：每個節點的左右子樹的高度之差為 0 或 1。

2. 二叉搜索樹

這些樹結構是非線性的，一個節點連接到多個節點。 該節點最多可以連接兩個子節點。 它被稱為二叉搜索樹，因為：

• 每個節點最多有兩個子節點。
• 它可用於在 0(log(n)) 時間內搜索元素，因此稱為搜索樹。

圖：二叉搜索樹示例 ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

二叉搜索樹的屬性是：

• 左子樹的所有節點中的值應小於根節點中的值。
• 右子樹的所有節點的值都應該大於根節點的值。

3.AVL樹

AVL 樹是二叉樹的類型或變體。 它由來自二叉樹和二叉搜索樹的屬性組成。 由 Adelson Velsky Lindas 發明，這些樹是自平衡的，這意味著左子樹和右子樹的高度是平衡的。 這種平衡是根據平衡因子來衡量的。

平衡係數：

• 它是左子樹和右子樹之間的差異。
• 平衡因子的值必須是 0、-1 或 1。因此，AVL 樹的每個節點都應包含一個平衡因子值，即 0、-1 或 1。
• 平衡因子 =（左子樹高度 - 右子樹高度）
• 如果每個節點的平衡因子在 -1 到 1 之間，則稱 AVL 樹為平衡樹。

AVL 樹中除 -1 到 1 以外的節點的值將表示需要平衡的不平衡樹。

• 如果一個節點的平衡因子為 1，則意味著左子樹比右子樹高一級。
• 如果一個節點的平衡因子為0，則表示左子樹和右子樹的高度相等。
• 如果一個節點的平衡因子為-1，則表示右子樹比左子樹高一級或左子樹比右子樹低一級。

4. B樹

B 樹是二叉搜索樹的一種更通用的形式。 它也被稱為高度平衡的 m 路樹，其中 m 是樹的階數。 樹的每個節點可以有多個鍵和兩個以上的子節點。 在二叉樹的情況下，葉節點可能不在同一級別。 但是，在 B 樹的情況下，所有葉節點都應該在同一級別。

B樹的屬性：

• 每個節點 x 的密鑰按升序存儲。
• 每個節點中都存在一個布爾值“x.leaf”，如果 x 是葉子，則為真。
• 內部節點最多應該有“n-1”個鍵，其中 n 是樹的順序。 它還應該為每個孩子提供一個指針。
• 除根節點外，所有節點最多有 n 個子節點和至少 n/2 個子節點。
• 樹的葉節點具有相同的深度。
• 根節點將至少有 1 個密鑰和至少兩個子節點。
• 如果 n ≥ 1，那麼對於任何高度為 h 且最小度為 t ≥ 2 的 n-key B 樹，h ≥ logt (n+1)/2。

應用

• 二叉搜索樹可用於在一組元素中搜索一個元素。
• 堆樹用於堆排序。
• 現代路由器使用一種稱為 Tries 的樹來存儲路由信息。
• B-Trees 和 T-Trees 主要被流行的數據庫用來存儲它們的數據。
• 編譯器使用語法樹來驗證每個編寫程序的語法。

結論

數據結構提供了一種有組織的方式來存儲數據，以便於管理和有效處理。 針對不同類型的數據存在各種類型的數據結構。 根據需要存儲的數據類型，由用戶選擇。

樹是這種數據結構的類型，其中可以存儲分層類型的數據。 數據存儲在節點中，這些節點有時存儲稱為子節點的其他節點的引用。

根據子節點的數量，樹可以分為文章中提到的各種類型。 基於樹類型中節點的排列，每個樹結構都有相關的屬性。 由於不同類別的樹可以執行不同類型的操作，這種類型的數據結構已經在排序算法和數據存儲中找到了應用。

由 upGrad 和 IIIT-Bangalore 策劃的軟件開發執行 PG 計劃 - 全棧開發專業化，可以幫助您提高個人資料並獲得更好的程序員就業機會。