[課業] BST 參考
這篇會講解一下部份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
推
12/27 23:08, , 1F
12/27 23:08, 1F
推
12/27 23:31, , 2F
12/27 23:31, 2F
※ 編輯: yantchen 來自: 120.127.36.183 (12/28 00:46)
推
12/28 17:50, , 3F
12/28 17:50, 3F