• Binary Tree
  • Difference with Tree
  • Three Theories of Binary Tree
    • [定理一] 第 i Level 最多 Node 數
    • [定理二] Height 為 k 的最多 Node 數 (整棵樹)
    • [定理三] Branch(Degree) 與 Node 關係
  • Type of Binary Tree
    • Skewed Tree - 斜曲樹
    • Complete Binary Tree
    • Strictly binary tree
    • Full Binary Tree
  • Binary Tree Representation in C
    • Array
    • Linked List
  • Binary Tree Traversal
  • Multiple Structures of One Binary Tree
    • Formula
  • Proof

Binary Tree

• 又稱為 Knuth Tree , Ordered Tree
• 有限集合，可以為空
• 若非空則由 左子樹、右子樹 構成
• 每個 Node 之 Degree：0~2
• 子樹 有次序之分

次序

1. 子樹 B,C 在 Tree 中視為相同
2. 在 Binary Tree 中視為不同
   

---

Difference with Tree

	Tree	Binary Tree
可否為空	$No$ , 至少一樹根	$Yes$
$NodeDegree$ (存在 $Root$ 時)	$\ge 0$	$0,1,2$

---

Three Theories of Binary Tree

[定理一] 第 i Level 最多

$Node$ 數

Def : 高度起始點為 1
Formula：

$2^{i-1}，i\ge 1$

證明方式：數學歸納法

Def : 高度起始點為 0
Formula：

$2^i，i\ge 0$

證明方式：數學歸納法

---

[定理二] Height 為 k 的最多 Node 數 (整棵樹)

Def : 高度起始點為

$1$
Formula：

$2^k-1,k\ge 1$

根據定理一：2⁰ + 2¹ + … + 2^k-1 從 Level 1 依序累加至 Level k

根據等比級數 =

$\frac{2^k-2^0}{2-1}$

=

$2^k-1$

Def : 高度起始點為

$0$
Formula：

$2^{(k+1)}-1,k\ge 0$

根據定理一：

$2^0+2^1+...+2^k$ 從

$Level0$ 依序累加至

$Levelk$

根據等比級數

$=\frac{2^{(k+1)}-2^0}{2-1}$

=

$2^{(k+1)}-1$

藉由上述定理我們可以對 Node 數取 log 反推回高度

---

[定理三] Branch(Degree) 與 Node 關係

• Leaf 數 = L (綠色node)
• Branch 數 = B (藍、紅 Degree)
• Nodes 數 = N
• Degree 為 1 的 Nodes = d₁ (藍色node)
• Degree 為 2 的 Nodes = d₂ (紅色node)

在上述圖例得知

1. $L+d_1+d_2=Node$ 總數

2. 二元樹中 Degree 為 0~2 ( 之後的 m-way Tree 同理 )
   Degree 為 1 的 Node 有 1 個 Branch
   Degree 為 2 的 Node 有 2 個 Branch
   而

   $(Branch$
   $\mathrm{數})$
   $+1=Node$ 總數
   所以
   $(1\ast d_1+2\ast d_2)+1=Node$ 總數

3. 藉由上述兩公式我們可以整理出
   

   $L+d_1+d_2=Node\mathrm{總}\mathrm{數}=d_1+2d_2+1$
   
   $L=d_2+1$
   $(\mathrm{樹}\mathrm{葉}=Degree\mathrm{為}2\mathrm{的}Nodes+1)$

---

整理一下目前有的公式

• Def : 高度起始點為 1

  1. 第 i Level 最多 Node 數：
     $2^{k-1}$ –––––-( 2的高度-1次方 )
  2. Height 為 k 的最多 Node 數：
     $2^k-1$ ––( 2的高度次方-1 )
  3. Node總數 =
     $L+d_1+d_2$ –––––––( 樹葉 + Deg1的Nodes + Deg2的Nodes )
  4. Node總數 = (
     $1\ast d_1+2\ast d_2)+1$ ––( 1倍Deg1的Nodes + 2倍Deg2的Nodes +1 )
  5. Node總數 =
     $Branch+1$ ––––––––( 分支+1 )
  6. 樹葉 =
     $d_2+1$ ––––––––––––––-( Deg2的Nodes+1 )
  7. Branch = 所有 Degree 合

補充：針對 3. 4. 的設計題
某樹之

$Degreeoftree=k$ ( 最大Degree 為k )

$Degree\mathrm{為}i$ 的

$Nodes$ 有

$i$ 個 ，

$1\le i\le k$， 求

$Leaf$ 總數？

Sol：

1. 根據 3.

   $Nodes=Deg-0$ 個數
   $(Leaf)+Deg-1$ 個數
   $+...+Deg-i$ 個數

2. 從題目

   $1\le i\le k$ 得
   $Nodes=Leaf+1+2+...+k$
   根據等差級數
   $Nodes=Leaf+$

3. 根據 4. Nodes = ( 1 * d₁ + 2 * d₂ ) + 1
   從題目

   $Degree\mathrm{為}i\mathrm{的}Nodes\mathrm{有}i\mathrm{個}$ 得 ( 1 * 1 + 2 * 2 + … + k * k ) + 1
   根據平方合 Nodes =

4. 移項即可得 Leaf =

關鍵字 Degree-0 (Leaf) , Degree-1 , Degree-2 , Height , Nodes , Branch 互通到熟練吧

---

Type of Binary Tree

Skewed Tree - 斜曲樹

• 左斜曲：每個非樹葉節點只有左子點。
• 右斜曲：每個非樹葉節點只有右子點。

---

Complete Binary Tree

• 由上至下由左而右依序填入
  
  

• Def：編號 (Index) 起始點 1 , 某Node編號 = n
  Left Child 編號 = Parent 編號 * 2
  Right Child 編號 = Parent 編號 * 2 + 1
  n's Parent 編號 =
  $\lceil \frac{(n-1)}{2}\rceil$

• Def：編號 (Index) 起始點 0 , 某Node編號 = n
  Left Child 編號 = Parent 編號 * 2 + 1
  Right Child 編號 = Parent 編號 * 2 + 2
  n's Parent 編號 =
  $\lfloor \frac{(n-1)}{2}\rfloor$

[color=#] 計算完請判斷該樹是否存在此節點
Parent , Child 編號關係證明：數學歸納法（略）

Def：高度起始點 1

• 根據定理二得出 k Level 的最大 Node 總數 =
  $2^k-1$
• 根據 Complete Binary Tree 特性，若高度
  $k$ ，則
  $Nodes$ 必介於
  
  $k$ 層第
  $1$ 個：
  $(2^{k-1}-1)+1$ (藍色 Nodes) 到
  
  $k$ 層最後一個 ：
  $2^k-1$
  $Nodes$ 之間

• 因此我們得知，給定一 Complete Binary Tree

  $2^{k-1}\le Nodes\le 2^k-1$

---

Strictly binary tree

• 除了 Leaf 以外，每個 Node 都有兩個 Child。
• $Nodes=n_0+n_2$

---

Full Binary Tree

• 長滿整棵樹，Nodes 等同定理二

---

Binary Tree Representation in C

Array

Def：編號 (Index) 起始點 1 , 高度 = k

1. 假設 k = 3
2. 建立一個 int tree[] 陣列，空間為：2^k-1 = 8 = s
   Index：0 ,1 ,2 ,3 ,4 ,5 ,6 ,7
3. 若使用迴圈，終止條件為
   • i<2^k-1 = 8-1 = s-1
   • i<=2^k-2 = 8-2 = s-2
4. 存在情況下，設某點為 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

1. 假設 k = 3
2. 建立一個 int tree[] 陣列，空間為：2^k+1-1 = 8 = s
   Index：0 ,1 ,2 ,3 ,4 ,5 ,6 ,7
3. 若使用迴圈，終止條件為
   • i<2^k+1-1 = 8-1 = s-1
   • i<=2^k+1-2 = 8-2 = s-2
4. 存在情況下，設某點為 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]

優點：

1. 容易存取左右 Child
2. 若 Perfect Binary Tree 則完美利用空間 (Def：root start from index 0)

缺點：

1. 插入、刪除 不便
2. Height 改變則需重新宣告新陣列
3. 對於 Skewed Binary Tree 極為浪費
   ( Def：root start from index 0 , Height = k = Nodes , 2^k-1-k 未使用)

---

Linked List

Def：Nodes = n

1. Linked List 中的 Link 相當於定理所提到的 Branch
   而在程式當中每個 Node 結構都有兩條 Link，有別於定理中的觀念
   我們會將指向 Null 的 Link 也一併算進去 (藍Link)
   實際上公式還是可行的，只要我們將 Null 也視為 Node

2. 不過我們想探討的是沒有使用到的 Link (藍Link)
   以下將 Branch 視為 Link

3. Links = 所有 Degree 合
   因為每一個 Node 皆有 2 個 Links
   => 所有的 Links = 2*n

4. 根據定理
   有使用到的 Links = n - 1

5. 根據 3. 4.得出
   =>所有的 Links - 有使用到的 Links = 未使用的 Links
   => (2 * n) - (n-1) = n+1

6. 可以這樣記 n-1 (未使用的LINK) -> n (Nodes) -> n+1 (使用的LINK)

優點：

1. Node 插入、刪除方便
2. 對於 Skewed Binary Tree 完美利用空間

缺點：

1. 各 Node Parent 不好尋找
2. 幾乎有
   $50\mathrm{\%}Links$ 未使用到，即指向
   $NULL$ 的
   $Link$
   (因此延伸出了 Threaded Binary Tree - 引線二元樹)

---

Binary Tree Traversal

• to be continued

---

Multiple Structures of One Binary Tree

• 回憶一下，以下兩種結構的樹，如果是 Tree 那麼兩顆是一樣的，如果是 Binary Tree 則是不同的

• 此節探討的就是當 Binary Tree 具有 N Nodes (N

  $\ge$ 1)，那麼這棵樹有幾種表示的方法，也就是他有幾種不同的結構

---

Formula

• ${\displaystyle \frac{1}{n+1}}$
  $\left(\begin{array}{c}2n\\ n\end{array}\right)$

• 給 3 Nodes 畫出所有的可能的 Binary Tree

• Solution：
  ${\displaystyle \frac{1}{3+1}}$
  $\left(\begin{array}{c}2\ast 3\\ 3\end{array}\right)=5$

Proof

to be continued
p.194

---

tags: Data Structure