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