數據結構中的二叉樹：屬性、類型、表示和好處

在不同類型的數據結構中，二叉樹比大多數其他類型的用途更多。 它們最顯著的應用包括點對點編程、搜索、密碼學、帶寬比其他網絡路由器更高的網絡路由器以及 3D 視頻遊戲。 我們現在將詳細討論數據科學中的二叉樹是什麼，它們的類型是什麼，以及它們是如何表示的。

什麼是二叉樹？

如果您以前研究過普通樹，甚至了解它們的基礎知識，您就會知道在這些樹中允許不同節點擁有的子節點數量方面沒有限制。 在這個意義上，二叉樹有點不同。 二叉樹中的每個父節點或節點最多只能有兩個子節點。

二叉樹中的所有節點都具有三個主要組件 -

• 一個數據元素
• 正確的參考
• 左參考

位於樹頂部的節點稱為根節點。 父節點是那些有子節點的節點。 子節點和父節點通過引用相互連接。 沒有任何子節點的節點稱為葉節點。

很明顯，二叉樹中的節點可以有一個孩子、兩個孩子或根本沒有孩子。 二叉樹不是線性數據結構，如隊列、數組、堆棧和鍊錶。 相反，它們是分層數據結構。

查看：面向初學者的數據科學項目創意

二叉樹節點的重要屬性

更好地理解這些屬性將幫助您充分利用關於二叉樹的討論。 不同節點的深度定義為將根連接到特定節點的路徑上存在的節點數。 這就是為什麼根節點的深度為 0。另一方面，二叉樹中不同節點的高度是位於連接特定節點和根節點的路徑中的節點數。 這就是葉節點高度為0的原因。

如您所見，節點的深度是通過從根節點開始然後向下到達該節點來測量的。 另一方面，在計算高度時，我們從相關節點開始，然後前往根節點。 兩次，我們都是從 0 開始。有些人也從 1 開始測量高度和深度，而不是從 0 開始，這沒有錯，這正是不同的人喜歡的。

現在節點的最大深度定義為二叉樹的深度。 類似地，節點的最大高度定義為二叉樹的高度。 所以二叉樹的高度和深度總是相同的。

了解更多： Python 中的數據結構和算法

什麼是二叉搜索樹？

二叉搜索樹是所有其他類型的二叉樹中最常見的。 它是一種專門的二叉樹，具有與任何其他形式的二叉樹不同且更有用的屬性。 究竟什麼是二叉搜索樹或 BST？ 顧名思義，二叉搜索樹用於在樹中搜索數據。

BST 具有允許它促進有效搜索的屬性。 BST是一棵二叉樹，其節點的鍵分別小於和大於右子樹中的節點和左子樹中的節點。

二叉樹的表示

1. 關聯表示

鏈接表示中的二叉樹作為鍊錶存儲在內存中。 這些列表的節點不存儲在相鄰或相鄰的內存位置，並且通過與樹相關聯的父子關係相互鏈接。

在這個表示中，每個節點都有三個不同的部分——

• 指向右節點的指針，
• 指向左節點的指針，
• 數據元素。

這是更常見的表示。 所有二叉樹都包含一個指向根節點方向的根指針。 當您看到一個根節點指向 null 或 0 時，您應該知道您正在處理一個空二叉樹。 左右指針存儲樹的左右子節點的地址。

2. 順序表示

儘管它比鏈接表示更簡單，但它的低效率使其成為兩者中不太受歡迎的二叉樹表示。 低效率在於存儲不同樹元素所需的空間量。 順序表示使用數組來存儲樹元素。

二叉樹的節點數定義了所使用的數組的大小。 二叉樹的根節點位於數組的第一個索引處。 存儲特定節點的索引將定義存儲節點的左右子節點的索引。 一棵空樹的第一個索引為 null 或 0。

二叉樹的類型

1. 完全二叉樹：完全二叉樹是那些節點要么有兩個孩子要么沒有孩子的二叉樹。 換句話說，當除了葉子之外，它的所有其他節點都有兩個孩子時，二叉樹就變成了完整的二叉樹。
2. 完全二叉樹：完全二叉樹是那些所有不同層次都被完全填充的樹。 唯一的例外可能是它們的最後一層，其鍵主要位於左側。 二叉堆通常被視為完整二叉樹的示例。
3. 完美二叉樹：完美二叉樹是葉子在同一層，內部節點攜帶兩個孩子的二叉樹。 完美二叉樹的一個常見例子是祖先家譜。
4. 病態退化二叉樹：退化樹是那些內部節點有一個孩子的二叉樹。 它們的性能水平類似於鍊錶。 了解有關二叉樹類型的更多信息。

閱讀： R 中最常用的六種數據結構

二叉樹的好處

1. 採用分層存儲數據的理想方式
2. 反映給定數據集中存在的結構關係
3. 使插入和刪除比鍊錶和數組更快
4. 一種靈活的保存和移動數據的方式
5. 用於存儲盡可能多的節點
6. 在訪問元素時比鍊錶快，比數組慢

結論

在這篇博客中，我們討論了數據結構中的二叉樹是什麼，並討論了它們的類型、表示形式和好處。 樹的兩個主要用途是搜索和存儲數據，因此它們是數據科學及其相關領域研究不可或缺的一部分。

如果您想了解數據結構、數據科學中的二叉樹，請查看 IIIT-B 和 upGrad 的數據科學執行 PG 計劃，該計劃專為在職專業人士創建，提供 10 多個案例研究和項目、實用的實踐研討會、與行業專家的指導，與行業導師的一對一，與頂級公司的 400 多個小時的學習和工作協助。