# 正課第三次作業

###### tags: `NTOU CSE C++ Programming`

> 教學文件和作業說明文件： https://hackmd.io/@kogiokka/ntou-cse-cpp-nav

> 範例程式和範例專案：[Google Drive](
https://drive.google.com/drive/folders/100YvcqccLgY_27mJnubRSuPALrMAghJQ?usp=sharing)

撰寫二元樹（binary search tree）程式來儲存各式的資料，並練習 C++ 語法：structure、pointer、reference 和 template。

程式範例：`binary-tree.cpp`

## 作業規定

* 繳交日期：5月13日
* 電子檔繳交方式：將程式碼和心得壓縮成 ZIP 檔上傳到教師的伺服器。檔案格式為`<學號>-<姓名>.zip`，例如：`11057666-陳小明.zip`。
* 紙本繳交方式：上課交紙本（A4紙）的程式碼和心得

## 題目

### 一、以二元樹儲存 `int`、`float`
###### 70 分

利用 template 的語法撰寫二元樹，儲存資料型態為 `int` 或 `float`。
必須使用下面結構

template<typename T>
struct TreeNode
{
    T data;
    struct TreeNode* left;
    struct TreeNode* right;
};

程式包含下列函式以及函式模板：

/**
 * 比較兩個數值的大小。
 *
 * @param a     數值一
 * @param b     數值二
 * @return      0 代表兩個數值相等；<0 代表 a 小於 b；>0 代表 a 大於 b。
 */
int compare(int a, int b);      // 比較int資料大小
int compare(float a, float b);  // 比較float資料大小

/**
 * 印出數值。
 * 
 * @param a    想要印出的數值
 */
void print(int a);
void print(float a);

/**
 * 新增一個值到指定的樹或子樹中
 * 
 * @param root    樹或子樹的根
 * @param value   欲插入的值
 */
template<typename T>
void insertNode(TreeNode<T>*& root, T value);

/**
 * 中序走訪（In-order Traversal）
 * 
 * @param root    樹或子樹的根
 */
template<typename T>
void inOrder(TreeNode<T>* root);

/**
 * 前序走訪（Pre-order Traversal）
 * 
 * @param root    樹或子樹的根
 */
template<typename T>
void preOrder(TreeNode<T>* root);

/**
 * 後序走訪（Post-order Traversal）
 * 
 * @param root    樹或子樹的根
 */
template<typename T>
void postOrder(TreeNode<T>* root);

### 二、以二元樹儲存結構（struct）
###### 20分

利用template語法撰寫的二元樹（binary search tree）來儲存書籍資料。書籍資料必須使用下面結構：

struct Book
{
    char* bookName;  // 書名當成 key 來比較大小
    char* authors; 
    int price; 
};

> Hint：每一種資料型別都有專門用於該型別的比大小函式。

// Use reference to avoid copying
int compare(const Book& book1, const Book& book2) { /* TODO */ }
inline void print(const Book& book) { /* TODO */ }

書籍資料範例：

| 名稱 | 作者 | 價格 |
| - | - | - |
| "精通光學辨識技術：應用ABBYY FineReader 11 OCR"|"黃敦義" | 371
| "VISUAL FORTRAN程式設計與開發" | "張嘉強、陳鴻智" | 400
| "程式設計－使用C++" | "黃建庭" | 420
| "資料庫系統－MTA認證影音教學" | "李春雄" | 336
| "輕鬆搞定Google雲端技術：Maps.Android.App Engine.Cloud SQL與電子商務API實例解析" | "陳世興" | 560
| "人工智慧：智慧型系統導論(第三版) " | "李聯旺 廖珗洲 謝政勳" | 590
| "電腦網路概論(第二版)" | "陳雲龍" | 420
| "網際網路與電子商務(第三版)" | "朱正忠" | 450
| "資料庫系統理論－使用SQL Server 2008" | "李春雄" | 650
| "動畫圖解資料庫系統理論－使用Access 2010實作(第二版) " | "李春雄" | 600

### 三、刪除二元樹資料的功能

###### 20分

/**
 * 在二元樹中搜尋指定的資料，並刪除該節點。
 * 
 * @param root    二元樹的樹根指標
 * @param key     要刪除的資料的key
 * @return        成功或失敗
 */
template<typename T, typename K>
int deleteNode(TreeNode<T>*& root, K key) { /* TODO */ }