บทนำ
Binary Search Tree (BST) คือ binary tree ที่จัดเรียงแล้ว โดยทุกโหนดมีคุณสมบัติดังนี้:
- Right sub-tree ของโหนดมีคีย์มากกว่าคีย์ของ parent node
- Left sub-tree ของโหนดมีคีย์น้อยกว่าคีย์ของ parent node
- คีย์ทั้งหมดไม่ซ้ำกัน
- แต่ละโหนดมีลูกได้สูงสุดสองตัว
คำอธิบายคลาสและฟังก์ชัน
Begin
class BST ประกาศฟังก์ชันต่อไปนี้:
search() = ค้นหา item ใน BST
เริ่มต้น temp = root
while (temp != NULL)
เพิ่ม depth
ถ้า temp->info == data พิมพ์ data และ depth
ถ้า temp->info > data temp = temp->l
มิฉะนั้น temp = temp->r
insert() = แทรก item ลงในต้นไม้:
ถ้าต้นไม้ว่าง ใส่ data เป็น root
ถ้าต้นไม้ไม่ว่าง
ถ้า data < root ใส่เป็น left child
มิฉะนั้น ใส่เป็น right child
del() = ลบ item จากต้นไม้
casea() = เรียกจาก del() ถ้า l = r = null
caseb() = เรียกจาก del() ถ้า l != null, r = null
caseb() = เรียกจาก del() ถ้า l = null, r != null
casec() = เรียกจาก del() ถ้า l != null, r != null
inorder() traverse แบบ inorder: left – root – right
preorder() traverse แบบ preorder: root – left – right
postorder() traverse แบบ postorder: left – right – root
End
ตัวอย่างโค้ด C++
#include <iostream>
#include <cstdlib>
using namespace std;
struct node {
int info;
struct node *l;
struct node *r;
} *root;
class BST {
public:
void search(node *, int);
void find(int, node **, node **);
void insert(node *, node *);
void del(int);
void casea(node *, node *);
void caseb(node *, node *);
void casec(node *, node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void show(node *, int);
BST() { root = NULL; }
};
void BST::find(int item, node **par, node **loc) {
node *ptr, *ptrsave;
if (root == NULL) {
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info) {
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->l;
else
ptr = root->r;
ptrsave = root;
while (ptr != NULL) {
if (item == ptr->info) {
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->l;
else
ptr = ptr->r;
}
*loc = NULL;
*par = ptrsave;
}
void BST::search(node *root, int data) {
int depth = 0;
node *temp = new node;
temp = root;
while (temp != NULL) {
depth++;
if (temp->info == data) {
cout << "\nData found at depth: " << depth << endl;
return;
} else if (temp->info > data)
temp = temp->l;
else
temp = temp->r;
}
cout << "\n Data not found" << endl;
return;
}
void BST::insert(node *tree, node *newnode) {
if (root == NULL) {
root = new node;
root->info = newnode->info;
root->l = NULL;
root->r = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (tree->info == newnode->info) {
cout << "Element already in the tree" << endl;
return;
}
if (tree->info > newnode->info) {
if (tree->l != NULL)
insert(tree->l, newnode);
else {
tree->l = newnode;
(tree->l)->l = NULL;
(tree->l)->r = NULL;
cout << "Node Added To Left" << endl;
return;
}
} else {
if (tree->r != NULL)
insert(tree->r, newnode);
else {
tree->r = newnode;
(tree->r)->l = NULL;
(tree->r)->r = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
void BST::del(int item) {
node *par, *loc;
if (root == NULL) {
cout << "Tree empty" << endl;
return;
}
find(item, &par, &loc);
if (loc == NULL) {
cout << "Item not present in tree" << endl;
return;
}
if (loc->l == NULL && loc->r == NULL) {
casea(par, loc);
cout << "item deleted" << endl;
}
if (loc->l != NULL && loc->r == NULL) {
caseb(par, loc);
cout << "item deleted" << endl;
}
if (loc->l == NULL && loc->r != NULL) {
caseb(par, loc);
cout << "item deleted" << endl;
}
if (loc->l != NULL && loc->r != NULL) {
casec(par, loc);
cout << "item deleted" << endl;
}
free(loc);
}
void BST::casea(node *par, node *loc) {
if (par == NULL) root = NULL;
else {
if (loc == par->l) par->l = NULL;
else par->r = NULL;
}
}
void BST::caseb(node *par, node *loc) {
node *child;
if (loc->l != NULL) child = loc->l;
else child = loc->r;
if (par == NULL) root = child;
else {
if (loc == par->l) par->l = child;
else par->r = child;
}
}
void BST::casec(node *par, node *loc) {
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->r;
while (ptr->l != NULL) {
ptrsave = ptr;
ptr = ptr->l;
}
suc = ptr;
parsuc = ptrsave;
if (suc->l == NULL && suc->r == NULL)
casea(parsuc, suc);
else
caseb(parsuc, suc);
if (par == NULL) root = suc;
else {
if (loc == par->l) par->l = suc;
else par->r = suc;
}
suc->l = loc->l;
suc->r = loc->r;
}
void BST::preorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
preorder(ptr->l);
preorder(ptr->r);
}
}
void BST::inorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
inorder(ptr->l);
cout << ptr->info << " ";
inorder(ptr->r);
}
}
void BST::postorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
postorder(ptr->l);
postorder(ptr->r);
cout << ptr->info << " ";
}
}
void BST::show(node *ptr, int level) {
int i;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout << endl;
if (ptr == root)
cout << "Root->: ";
else {
for (i = 0; i < level && ptr != root; i++)
cout << " ";
}
cout << ptr->info;
show(ptr->l, level + 1);
}
}
int main() {
int choice, num, item;
BST bst;
node *t;
while (1) {
cout << "1.Insert Element" << endl;
cout << "2.Delete Element" << endl;
cout << "3.Search Element" << endl;
cout << "4.Inorder Traversal" << endl;
cout << "5.Preorder Traversal" << endl;
cout << "6.Postorder Traversal" << endl;
cout << "7.Display the tree" << endl;
cout << "8.Quit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
t = new node;
cout << "Enter the number to be inserted: ";
cin >> t->info;
bst.insert(root, t);
break;
case 2:
if (root == NULL) {
cout << "Tree is empty, nothing to delete" << endl;
continue;
}
cout << "Enter the number to be deleted: ";
cin >> num;
bst.del(num);
break;
case 3:
cout << "Search:" << endl;
cin >> item;
bst.search(root, item);
break;
case 4:
cout << "Inorder Traversal of BST:" << endl;
bst.inorder(root);
cout << endl;
break;
case 5:
cout << "Preorder Traversal of BST:" << endl;
bst.preorder(root);
cout << endl;
break;
case 6:
cout << "Postorder Traversal of BST:" << endl;
bst.postorder(root);
cout << endl;
break;
case 7:
cout << "Display BST:" << endl;
bst.show(root, 1);
cout << endl;
break;
case 8:
exit(1);
default:
cout << "Wrong choice" << endl;
}
}
return 0;
}
ผลลัพธ์ตัวอย่าง
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice: 1 Enter the number to be inserted: 6 Root Node is Added ... (ตัวอย่างการทำงานต่อไป)
