Binary Tree

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

次序

  1. 子樹 B,C 在 Tree 中視為相同
  2. 在 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
可否為空
No
, 至少一樹根
Yes
NodeDegree
(存在
Root
時)
0
0,1,2

Three Theories of Binary Tree

[定理一] 第 i Level 最多
Node

Def : 高度起始點為 1
Formula

2i1 i1

證明方式:數學歸納法

Def : 高度起始點為 0
Formula

2i i0

證明方式:數學歸納法


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

Def : 高度起始點為

1
Formula
2k1 , k1

根據定理一:20 + 21 + + 2k-1 從 Level 1 依序累加至 Level k

根據等比級數 =
2k2021

=
2k1

Def : 高度起始點為

0
Formula
2(k+1)1 , k0

根據定理一:
20+21+ ... +2k
Level 0
依序累加至
Level  k

根據等比級數
=2(k+1)2021

=
2(k+1)1

藉由上述定理我們可以對 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)






graphname



1

Root



2

A



1->2





3

B



1->3





4

C



2->4





5

leaf



2->5





6

leaf



3->6





7

Null



3->7





8

leaf



4->8





9

Null



4->9





10

Null



5->10





11

Null



5->11





12

Null



6->12





13

Null



6->13





15

Null



8->15





16

Null



8->16





在上述圖例得知

  1. L+d1 +d2=Node 總數

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

    (Branch
    )
    +1=Node
    總數

    所以
    (1d1+2d2)+1=Node
    總數

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

    L+d1+d2=Node=d1+2d2+1
    L=d2+1
    ( =Degree  2  Nodes+1 )


整理一下目前有的公式

  • Def : 高度起始點為 1

    1. 第 i Level 最多 Node 數:
      2k1
      -( 2的高度-1次方 )
    2. Height 為 k 的最多 Node 數:
      2k1
      ( 2的高度次方-1 )
    3. Node總數 =
      L+d1+d2
      ( 樹葉 + Deg1的Nodes + Deg2的Nodes )
    4. Node總數 = (
      1d1+2d2)+1
      ( 1倍Deg1的Nodes + 2倍Deg2的Nodes +1 )
    5. Node總數 =
      Branch+1
      ( 分支+1 )
    6. 樹葉 =
      d2+1
      -( Deg2的Nodes+1 )
    7. Branch = 所有 Degree 合

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

Degree of tree=k ( 最大Degree 為k )
Degree  i
Nodes
i
個 ,
1ik
, 求
Leaf
總數?


Sol

  1. 根據 3.

    Nodes=Deg0 個數
    (Leaf)+Deg1
    個數
    +...+Degi
    個數

  2. 從題目

    1ik
    Nodes=Leaf+1+2+...+k

    根據等差級數
    Nodes=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 →

  3. 根據 4. Nodes = ( 1 * d1 + 2 * d2 ) + 1
    從題目

    Degree  i  Nodes  i ( 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 →

  4. 移項即可得 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 編號 =
    (n1)2
  • Def:編號 (Index) 起始點 0 , 某Node編號 = n
    Left Child 編號 = Parent 編號 * 2 + 1
    Right Child 編號 = Parent 編號 * 2 + 2
    n's Parent 編號 =
    (n1)2

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

Def:高度起始點 1

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






graphname



1

Root



2

A



1->2





3

B



1->3


     若 Level=3 則必含有藍Node



4

D



2->4





5

E



2->5





6

F



3->6





7

G



3->7


   紅 Node為
   Level=3 Node總數合理範圍



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

    2k1Nodes2k1


Strictly binary tree

  • 除了 Leaf 以外,每個 Node 都有兩個 Child。
  • Nodes=n0+n2


Full Binary Tree

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


Binary Tree Representation in C

Array

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

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






graphname



0

tree[0]



1

tree[1]



2

tree[2]



1->2





3

tree[3]



1->3





4

tree[4]



2->4





5

tree[5]



2->5





6

tree[6]



3->6





7

tree[7]



3->7






Def:編號 (Index) 起始點 0 , 高度 = k

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






graphname



0

tree[0]



1

tree[1]



0->1





2

tree[2]



0->2





3

tree[3]



1->3





4

tree[4]



1->4





5

tree[5]



2->5





6

tree[6]



2->6





7

tree[7]



優點:

  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 , 2k-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)







graphname



1

Root



2

A



1->2





3

B



1->3





4

leaf



2->4





5

leaf



2->5





6

leaf



3->6





7

leaf



3->7





8

Null



4->8





9

Null



4->9





10

Null



5->10





11

Null



5->11





12

Null



6->12





13

Null



6->13





14

Null



7->14





15

Null



7->15





優點:

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

缺點:

  1. 各 Node Parent 不好尋找
  2. 幾乎有
    50% 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

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


Formula

  • 1n+1
    (2nn)

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

  • Solution:
    13+1
    (233)=5

Proof

to be continued
p.194


tags: Data Structure