這篇會講解一下部份BST的功能怎麼實做 給沒頭緒的人參考 看懂後自己把剩下的功能寫出來 --- 要求的功能 1. 宣告 2. 新增 3. 查詢 4. 刪除 5. inorder顯示 --- 宣告最簡單 直接依照題目要求 class node { int value; node *left, *right; friend class tree; public: node(int v) { value = v; left = right = NULL; } }; class tree { node *root; public: tree() { root = NULL; } }; node 應該很容易理解 就是兩個鏈結的串列 tree 是我用來放root的地方 到時候連到樹的每個節點 還有所有的動作都會在 tree 裡面完成 為了讓 tree 能操作 node 的東西 在 node 裡面宣告 tree 成 friend --- 新增節點 演算法: 1. 從 root 開始 2. 判斷目前節點 跟 新輸入的值 若 大於, 目前節點 = 右節點 若 小於, 目前節點 = 左節點 3. 重複步驟 2, 直到 目前節點 == NULL 4. 插入新的節點在這裡 程式碼用遞迴寫就非常簡單 在 tree 的 public 裡面增加一個 add 函數 void add(int val) // 前置作業 { if(root == NULL) root = new node(val); else add(val, root); } void add(int val, node *n) // add 遞迴函數 { if(n->value < val) { if(n->right==NULL) n->right=new node(val); else add(val, n->right); } else { if(n->left ==NULL) n->left =new node(val); else add(val, n->left ); } } 主程式只要呼叫 int main() { tree T; T.add(10); T.add(12); ... } --- 再講一個inorder吧 演算法也非常簡單 1. 從 root 開始 2. 有左邊就跳到左邊 3. 顯示自己 4. 跳到右邊 在 tree 裡面新增一個 public 的 show 函數 void show() // 前置作業 { if(root == NULL) { cout << "這棵樹沒有樹葉 是棵枯枯的樹"; } else { show(root); } } void show(node *n) // show 的遞迴函數 { if(n->left != NULL) show(n->left); cout << n->value << '\t'; if(n->right != NULL) show(n->right); } --- 剩下功能自己想想看 除了 del 比較難 其實其他的都很簡單唷 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 120.127.36.183 ※ 編輯: yantchen 來自: 120.127.36.183 (12/28 00:46)