昨天介紹了很多跟樹狀結構有關的名詞，今天開始介紹不同種類的樹吧ヽ(✿ﾟ▽ﾟ)ノ

二元樹(Binary Tree)

定義

• 可以為空集合
• 若不為空，則有root及左子樹、右子樹
• 左、右子樹也是Binary Tree
• 分支度為0≤d≤2
• 有次序關係，左節點會排在右節點之前，不能顛倒

種類

1. skewed B.T. (歪斜樹)
   可分為兩種

   • left-skewed B.T.:每個節點都只有左子點，無右子點
     (圖)
   • right-skewed B.T:每個節點都只有右子點，無左子點
     (圖)

2. Full B.T. (完滿二元樹)
   高度為k之B.T.，具有最多node數:2ᵏ-1
   (圖)

3. Complete B.T. (完整二元樹)
   高度k，Node數=n的二元樹，滿足:
   (1)2ᵏ⁻¹ -1 < n < 2ᵏ-1
   (2)Node編號順序與高度k的Full B.T.的前n個Nodes編號一一對應(即Node的增長需是由上而下，由左而右依序增長)
   (圖)

Binary Tree之三個基本定理(令Root level=1)

[定理一]

二元樹中第i level之最多node數=2ⁱ⁻¹個(i≥1)

(圖)
<證明>數學歸納法
1.當level=1時，最多只有Root一個點，所以符合2¹⁻¹=2⁰=1，初值成立
2.令level=(i-1)時，此定理成立
3.當level=i時，其最多Node數必定=(第(i-1)level之最多Node數)×2 = 2ⁱ⁻¹⁻¹ ×2 =2ⁱ⁻¹
4.Hence，由1、2、3及數學歸納法得証

[定理二]

高度為k之二元樹，其最多Node數=2ᵏ-1

<證明>
(圖)
=2⁰+2¹+2²+...+2ᵏ-1 = (2ᵏ⁻¹⁺¹-2⁰)/(2-1) = 2ᵏ-1

定理二之反向

若二元樹有n個nodes則最大高度=n，最小高度為?
(圖)

[定理三]

給予一個非空的B.T.，若leaf各數有n₀個，Degree-2之node數有n₂個，則n₀=n₂+1

(圖)
<證明>
假設
n:代表node總數
n₁:代表Degree-1之node數
B:代表Branch(分支)總數(即有用的link數，邊數)(即B=n-1)
所以
n = n₀ + n₁ + n₂
= B + 1
= [1×n₁+2×n₂]+1
n₀=n₂+1

Binary Tree與Tree之比較