二元樹.ppt

Algorithms (Dr. Shi-Jay Chen, National United University) Course 0課程介紹Introduction ? Outline 了解本課程授課重點、目標及課程設計 了解本課程評分標準 課前重點 資料結構 v.s. 演算法 資料結構概念基礎複習 ? 教材 Text Book 蔡宗翰, 演算法: 使用C++ 虛擬碼, 碁峰圖書, 2004. 講義下載處: .tw/~sjchen Reference Book R. E. Neapolitan and K. Naimipour, Foundations of Algorithms: Using C++ Pseudocode, 3/e, Jones, 2004. (Textbook原文本) 李家同教授, Computational Biology, 全文電子書第二章. 洪逸, 洪捷, 演算法-名校攻略密笈, 鼎茂圖書. 洪逸, 資料結構(含精選試題), 鼎茂圖書. ? 課程重點 前置觀念 演算法：效率，分析與量級 (Algorithms: Efficiency, Analysis, and Order) 遞迴 (Recursion) 排序 (Sort) 搜尋 (Search) 解題策略 Divide-and-Conquer (切割與征服) Dynamic Programming (動態規劃) The Greedy Approach (貪婪法則) Backtracking (回溯) Branch-and-Bound (分枝與限制) NP問題 An Introduction to the Theory of NP ? 評分標準 期中考：35% 期末考：35% 平時考：20% 平時成績：10% 加分程式題：10%~20% ▓ 資料結構 v.s. 演算法 ▓ Array Def: 為表示有序的線性串列之一種方式 其佔用連續性的記憶體空間 各元素型態皆需相同 (一致) 支援Sequential及Random Access 插入、刪除元素較為麻煩 ∵需挪移其它元素 ?不易動態增刪空間大小 Array種類 一維陣列 二維陣列 三維陣列 N維陣列 ▓ Linked List Def: 由一組節點 (Node)所組成的有序串列，各Node除了Data欄之外，另外有 ≥ 1 個Link欄 (或稱 Pointer)，用以指向其它Node之位址。 有一個指標變數 (Pointer variable) 用來指出鏈結串列中的第一個節點之所在。指標變數的名字可用來做為其所指向之鏈結串列的名字。 Linked list的特質: 各Node不一定要佔用連續的Memory空間 各Node之型態 (Data Type) 不一定要相同 僅支援Sequential Access Insert/Delete Node 容易 ▓ Stack Def: 具有LIFO (last in-first out)或FILO (first in-last out) 性質的有序串列。 插入元素的動作稱為Push, 刪除元素的動作稱為Pop. Push/Pop的動作皆發生在同一端，此端稱為Top. ▓ Queue (佇列) Def: 具有FIFO (first in-first out) 性質的有序串列。其插入元素的動作稱為發生在Rear (尾)端, 刪除元素的動作發生在Front (前)端. ▓ Tree Def: Tree是由1個以上的Nodes所組成的有限集合，滿足: 至少有一個Node，稱為Root 其餘的Nodes分成T1, T2, …, Tn個互斥集合，稱為Subtree ▓ Binary Tree (二元樹) Def: Binary Tree為具有 ≥ 0 個nodes所構成的有限集合。 Binary Tree可以為空的樹。 若不為空的樹，則具有Root及左, 右子樹，且左, 右子樹亦是Binary Tree。 二元樹之三個基本定理 [定理一]: 二元樹中，第i個level的node個數最多有 2i-1 個。 [定理二]: 高 (深) 度為k的二元樹，其node個數最多有 2k-1 個。 [定理三]: 非空二元樹若leaf個數為 n0 個，degree為2的node個數為n2個，則 n0 = n2+1。 二元樹的種類 Skewed Binary Tree Full Binary Tree Complete Binary Tree Skewed Binary Tree Def: 可分為 Left-Skewed Binary Tree: 每個non-leaf node皆只有左子集 Right-Skewed Binary Tree: 每個non