資料結構（樹）

參考網站

演算法筆記

演算法動畫

Swift 演算法

樹的定義

樹是1對多的結構，沒有節點的樹稱為空樹

1.存在唯一的根節點(root)

2.其餘節點可成為另一棵樹或稱子樹，注意子樹互不相交

節點分類

一個節點的子樹數量稱為度

度為 0 表示此節點是葉子

階級

階級是從root開始算，根為一階並往下加

最大階度也稱為樹的深度或高度

樹的抽象資料型別

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
樹 (Tree)

Data
樹中節點有相同資料型態及階級關係

Operation
  InitTree(*T)       : 初始化
  DestroyTree(*T)    : 銷毀樹
  CreateTree(*T,def) : 根據 def 定義樹
  ClearTree(*T)      : 清空 Tree  
  TreeEmpty(T)       : 檢查 Tree 是否為空
  TreeDepth(T)       : 檢查 Tree 深度
  Root(T)            : 回傳 Tree 根節點
  Value(T,cur_e)     : 回傳此節點的值
  Assign(T,cur_e,val): 將節點值改變
  Parent(T,cur_e)    : 回傳節點雙親

二元樹

1.每個節點最多兩個子樹，所以沒有大於2度的節點

2.左子樹和右子樹是有順序的

3.即使只有一個子樹也要區分左右

特殊二元樹

斜樹:所有節點只有左子樹或右子樹

完滿二元樹(Full binary):所有葉子都在同一階，高度 h 要有 2^h-1 個 Node

完整二元樹(Complete binary):也就是高度 h 但 Node < 2^h-1 個 Node 的樹

實作二元樹

3 種實作二元樹的方法

1
2
3
陣列表示法(如果是斜樹會浪費空間)
結構陣列表示法(如果是斜樹會浪費空間)
鏈結表示法

走訪二元樹

走訪二元樹的順序很重要，每個 Node 只拜訪一次

主要分為下面 4 種走法，都用遞迴寫法

1
2
3
4
前序(PreOrder)
中序(InOrder)
後序(PostOrder)
階序