二子樹 (Binary Tree)
二子樹 (Binary Tree)
定義
二子樹是一種樹狀數據結構，其中每個節點最多有兩個子節點，分別稱為左子節點和右子節點。二子樹的每個節點包含三個部分：數據、左子節點的引用和右子節點的引用。
性質
- 每個節點最多有兩個子節點。
- 左子節點的值小於父節點的值，右子節點的值大於父節點的值。
- 二子樹的高度是從根節點到最遠葉子節點的最長路徑上的節點數。
範例
以下是一些簡單的二子樹範例：
範例1：
5
/ \
3 7
/ \ / \
2 4 6 8
範例2：
10
/ \
5 15
/ \ / \
3 7 12 18
範例3：
20
/ \
10 30
/ \ / \
5 15 25 35
範例4：
8
/ \
4 12
/ \ / \
2 6 10 14
範例5：
25
/ \
20 30
/ \ / \
15 22 28 35
在這些範例中，每個節點的左子節點的值都小於父節點的值，右子節點的值都大於父節點的值。
應用
二子樹在計算機科學中有許多應用，包括：
- 搜索樹：二子樹可以用來實現高效的搜索操作。
- 排序：二子樹可以用來實現高效的排序算法，如快速排序和合併排序。
- 優先級隊列：二子樹可以用來實現優先級隊列，其中每個節點的優先級由其值決定。
重要性
二子樹在計算機科學中具有重要地位，因為它們提供了一種高效的數據結構來存儲和操作數據。通過使用二子樹，可以實現高效的搜索、插入和刪除操作，這對於許多應用程序來說是至關重要的。