正課第三次作業

tags: NTOU CSE C++ Programming

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

範例程式和範例專案：Google Drive

撰寫二元樹（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 */ }