Binary Tree
- 又稱為 Knuth Tree , Ordered Tree
- 有限集合,可以為空
- 若非空則由 左子樹、右子樹 構成
- 每個 Node 之 Degree:0~2
- 子樹 有次序之分
次序
- 子樹 B,C 在 Tree 中視為相同
- 在 Binary Tree 中視為不同
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Difference with Tree
|
Tree |
Binary Tree |
可否為空 |
, 至少一樹根 |
|
(存在 時) |
|
|
Three Theories of Binary Tree
[定理一] 第 i Level 最多 數
Def : 高度起始點為 1
Formula:
Def : 高度起始點為 0
Formula:
[定理二] Height 為 k 的最多 Node 數 (整棵樹)
Def : 高度起始點為
Formula:
根據定理一:20 + 21 + … + 2k-1 從 Level 1 依序累加至 Level k
根據等比級數 =
=
Def : 高度起始點為
Formula:
藉由上述定理我們可以對 Node 數取 log 反推回高度
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
[定理三] Branch(Degree) 與 Node 關係
- Leaf 數 = L (綠色node)
- Branch 數 = B (藍、紅 Degree)
- Nodes 數 = N
- Degree 為 1 的 Nodes = d1 (藍色node)
- Degree 為 2 的 Nodes = d2 (紅色node)
在上述圖例得知
-
總數
-
二元樹中 Degree 為 0~2 ( 之後的 m-way Tree 同理 )
Degree 為 1 的 Node 有 1 個 Branch
Degree 為 2 的 Node 有 2 個 Branch
而 總數
所以 總數
-
藉由上述兩公式我們可以整理出
整理一下目前有的公式
-
Def : 高度起始點為 1
- 第 i Level 最多 Node 數: –––––-( 2的高度-1次方 )
- Height 為 k 的最多 Node 數: ––( 2的高度次方-1 )
- Node總數 = –––––––( 樹葉 + Deg1的Nodes + Deg2的Nodes )
- Node總數 = ( ––( 1倍Deg1的Nodes + 2倍Deg2的Nodes +1 )
- Node總數 = ––––––––( 分支+1 )
- 樹葉 = ––––––––––––––-( Deg2的Nodes+1 )
- Branch = 所有 Degree 合
補充:針對 3. 4. 的設計題
某樹之 ( 最大Degree 為k )
的 有 個 ,, 求 總數?
Sol:
-
根據 3.
個數 個數 個數
-
從題目 得
根據等差級數
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
根據 4.
Nodes = ( 1 * d1 + 2 * d2 ) + 1
從題目 得 ( 1 * 1 + 2 * 2 + … + k * k ) + 1
根據平方合 Nodes =
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
移項即可得 Leaf =
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
關鍵字 Degree-0 (Leaf) , Degree-1 , Degree-2 , Height , Nodes , Branch 互通到熟練吧
Type of Binary Tree
Skewed Tree - 斜曲樹
- 左斜曲:每個非樹葉節點只有左子點。
- 右斜曲:每個非樹葉節點只有右子點。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Complete Binary Tree
- 由上至下由左而右依序填入

- Def:編號 (Index) 起始點 1 , 某Node編號 = n
Left Child 編號 = Parent 編號 * 2
Right Child 編號 = Parent 編號 * 2 + 1
n's Parent 編號 =
- Def:編號 (Index) 起始點 0 , 某Node編號 = n
Left Child 編號 = Parent 編號 * 2 + 1
Right Child 編號 = Parent 編號 * 2 + 2
n's Parent 編號 =
[color=#] 計算完請判斷該樹是否存在此節點
Parent , Child 編號關係證明:數學歸納法(略)
Def:高度起始點 1
- 根據定理二得出 k Level 的最大 Node 總數 =
- 根據 Complete Binary Tree 特性,若高度 ,則 必介於
層第 個: (藍色 Nodes) 到
層最後一個 : 之間
Strictly binary tree
- 除了 Leaf 以外,每個 Node 都有兩個 Child。

Full Binary Tree

Binary Tree Representation in C
Array
Def:編號 (Index) 起始點 1 , 高度 = k
- 假設 k = 3
- 建立一個
int tree[]
陣列,空間為:2k-1 = 8 = s
Index:0 ,1 ,2 ,3 ,4 ,5 ,6 ,7
- 若使用迴圈,終止條件為
- i<2k-1 = 8-1 = s-1
- i<=2k-2 = 8-2 = s-2
- 存在情況下,設某點為 n
- Root =
tree[1]
- n's Parent =
tree[n/2]
* 請注意程式語言對浮點數處理特性
- n's Left Child =
tree[2*n]
- n's Right Child =
tree[2*n+1]
Def:編號 (Index) 起始點 0 , 高度 = k
- 假設 k = 3
- 建立一個
int tree[]
陣列,空間為:2k+1-1 = 8 = s
Index:0 ,1 ,2 ,3 ,4 ,5 ,6 ,7
- 若使用迴圈,終止條件為
- i<2k+1-1 = 8-1 = s-1
- i<=2k+1-2 = 8-2 = s-2
- 存在情況下,設某點為 n
- Root =
tree[0]
- n's Parent =
tree[(n-1)/2]
* 請注意程式語言對浮點數處理特性
- n's Left Child =
tree[2*n+1]
- n's Right Child =
tree[2*n+2]
優點:
- 容易存取左右 Child
- 若 Perfect Binary Tree 則完美利用空間 (Def:root start from index 0)
缺點:
- 插入、刪除 不便
- Height 改變則需重新宣告新陣列
- 對於 Skewed Binary Tree 極為浪費
( Def:root start from index 0 , Height = k = Nodes , 2k-1-k 未使用)
Linked List
Def:Nodes = n
-
Linked List 中的 Link 相當於定理所提到的 Branch
而在程式當中每個 Node 結構都有兩條 Link,有別於定理中的觀念
我們會將指向 Null 的 Link 也一併算進去 (藍Link)
實際上公式還是可行的,只要我們將 Null 也視為 Node
-
不過我們想探討的是沒有使用到的 Link (藍Link)
以下將 Branch 視為 Link
-
Links = 所有 Degree 合
因為每一個 Node 皆有 2 個 Links
=> 所有的 Links = 2*n
-
根據定理
有使用到的 Links = n - 1
-
根據 3.
4.
得出
=>所有的 Links - 有使用到的 Links = 未使用的 Links
=> (2 * n) - (n-1) = n+1
-
可以這樣記 n-1 (未使用的LINK) -> n (Nodes) -> n+1 (使用的LINK)
優點:
- Node 插入、刪除方便
- 對於 Skewed Binary Tree 完美利用空間
Binary Tree Traversal
Multiple Structures of One Binary Tree


Proof
to be continued
p.194