解釋了數據結構中的 5 種二叉樹

二叉樹是一種非線性樹數據結構，每個節點最多有 2 個子節點。 二叉樹的名稱表示數字 2，因此任何二叉樹都可以有左孩子和右孩子。

指針將二叉樹描繪到最上面的節點，通常稱為樹的根。 二叉樹中的每個節點都包含數據、指向左孩子的指針和指向右孩子的指針。 指針用於實現二叉樹。 根指針表示樹中的第一個節點。 為了創建二叉樹，您需要首先創建一個節點。

在熟悉了數據結構中什麼是二叉樹之後，你還需要了解二叉樹的基本操作。 您可以執行插入元素、刪除元素、搜索元素和遍歷二叉樹等功能。

數據結構中的任何二叉樹在計算中都以兩種不同的方式使用。 首先，它們用於根據與每個節點鏈接的特定標籤或值訪問節點。 其次，它們被用作具有相關分支結構的數據表示。

在了解各種二叉樹類型之前，讓我們先熟悉一下二叉樹中使用的術語。

節點：它在二叉樹中保存數據值。

根：任何二叉樹中最頂端的節點稱為樹的根。

大小：它表示二叉樹中的節點數。

父節點：二叉樹中帶有子節點的節點。

子節點：它是源自遠離二叉樹根的父節點的節點。

內部節點：它是二叉樹中至少有一個孩子的節點。

葉節點：它是一個沒有孩子的節點。它也可以是一個外部節點。

節點樹的深度：它是在特定節點的上下文中計算的。它被稱為從特定節點到根的邊數。

樹的內部路徑長度：指二叉樹中每個內部節點的層次之和。

一棵樹的外部路徑長度：它被定義為二叉樹中每個外部節點的層次之和。

樹中節點的高度：它是從特定節點到二叉樹最深葉節點的邊數。根的高度將始終大於二叉樹中其他節點的高度。

現在讓我們檢查一下 5種二叉樹的詳細信息。

二叉樹的類型

1. 滿二叉樹

這種數據結構中的二叉樹也被稱為 -Proper binary tree 和 Strict binary tree。 它是數據結構中最基本的二叉樹類型之一。 完整二叉樹被定義為二叉樹，其中每個節點應該有兩個或根本沒有孩子。

它也可以表徵為二叉樹，其中每個節點都包含除葉節點之外的兩個子節點。 存儲根節點地址的節點稱為根的子節點。 那些沒有子節點的節點稱為葉節點。

您需要遍歷所有節點以檢查樹是否為二叉樹。 如果任一節點有一個子節點，代碼將返回“False”。 如果所有節點都有 0 個或 2 個子節點，它將返回“True”。

以下是完整二叉樹的屬性：

• 葉子節點數等於內部節點數+1。例如，如果內部節點數為4，則葉子節點數等於5。
• 二叉樹的最大節點數和節點數相等。 它表示為2h+1 -1。
• 滿二叉樹的最小節點數是 2h-1。
• 滿二叉樹的最小高度是 log 2 (n+1) – 1。
• 滿二叉樹的最大高度為 h = (n+1)/2。

2. 完美二叉樹

完美二叉樹是其中一種二叉樹，其中每個節點必須有 0 或 2 個子節點，並且每個葉節點的級別必須相同。 換句話說，數據結構中的完美二叉樹被定義為所有內部節點都擁有兩個分支和那些沒有分支的節點（葉節點）存在於同一層的樹。

在這種情況下，節點的級別是距根節點的距離或高度。 您可以將完美二叉樹視為完全二叉樹，其中最後一層也被完全佔據。

從世界頂尖大學在線學習數據科學課程。 獲得執行 PG 課程、高級證書課程或碩士課程，以快速推進您的職業生涯。

3.完全二叉樹

完全二叉樹是數據結構中的那些類型的二叉樹之一，其中樹的所有級別都被完全填充。 二叉樹的最後一層可能會或可能不會被完全填滿。 但是，每個節點都必須位於節點最後一層的最左邊。 必須從左側開始包含節點。

它們是二叉樹的基本類型之一，因為它們提供了節點數與樹高之間的最佳比率。

以下是完整二叉樹的關鍵屬性：

• 最大節點數為 2 h+1 – 1。
• 最小節點數為 2 h 。
• 最小高度為 log 2 (n+1) – 1。

4. 平衡二叉樹

在平衡二叉樹中，樹的高度是節點總數的log 2 。 假設樹的高度為 h，樹的節點總數為 n。 計算高度的公式是 h = log(n)。 右子樹和左子樹之間的最大高度差必須為“1”。

差異可以有其他值，如 0 和 -1。 這些類型的二叉樹也稱為 AVL 樹。 平衡二叉樹的著名示例之一是紅黑樹。

您可以實現以下代碼來運行平衡二叉樹。

私有類節點 {

私有整數值；

私有節點離開；

私有節點權；

}

公共布爾isBalanced（節點n）{

如果（平衡樹高度（n）> -1）

返回真；

返回假；

}

public int balancedtreeHeight（節點 n）{

如果（n == null）

返回 0；

int h1 = balancedtreeHeight(n.right);

int h2 = balancedtreeHeight(n.left);

如果（h1 == -1 || h2 == -1）

返回-1；

如果 (Math.abs(h1 – h2) > 1)

返回-1；

如果 (h1 > h2)

返回 h1 + 1；

返回 h2 + 1；

}

檢查我們的美國 - 數據科學計劃

5. 退化二叉樹

退化二叉樹是一種不太常用的二叉搜索樹類型。 它是一棵二叉樹，其中每個節點只有一個孩子，即左孩子或右孩子。 任何節點都不應同時具有左右子節點。

閱讀我們的熱門美國 - 數據科學文章

結論

如果要將其用於各種應用程序，則必須了解什麼是數據結構中的二叉樹。 在二叉樹上實現不同的功能可以幫助您有效地組織和存儲數據。

研究多種類型的二叉樹可以幫助您在時間複雜度上更有效地執行操作。 數據科學基礎知識，包括二叉樹數據結構，可幫助您輕鬆開啟數據科學之旅。 隨後，您可以從事高級數據科學項目，以提高您的技能和作品集。

在 upGrad 上開始您的機器學習之旅

如果您想學習數據科學，可以攻讀 upGrad 的數據科學理學碩士課程。 這個為期 24 個月的課程傳授 Python、部署 ML 模型、使用 Spark 進行 BD 處理、預測分析和統計以及監督和非監督 ML 模型等技能。 該課程適合雄心勃勃的管理人員、MBA 畢業生、工程師和各個領域的專業人士。

完成本課程將幫助您成為數據工程師、大數據分析師、機器學習工程師和數據科學家。