นี่คือโปรแกรม C++ สำหรับหาจำนวนครั้งที่ตัวเลขที่กำหนดปรากฏ โดยใช้วิธี Binary Search
อัลกอริทึม
เริ่มต้น ฟังก์ชัน Insert() เพื่อแทรกโหนดลงในต้นไม้: อาร์กิวเมนต์: root, d ส่วนตัวของฟังก์ชัน: สร้างโหนดโดยใช้ข้อมูลจากอาร์กิวเมนต์ ถ้าต้นไม้ว่างเปล่าทั้งหมด ให้แทรกโหนดใหม่เป็น root ถ้า d = tmp->data เพิ่มจำนวนนับ (count) ของโหนดนั้น ถ้า d < tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกซ้าย ถ้า d > tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกขวา จบ เริ่มต้น ฟังก์ชัน SearchNode() เพื่อค้นหาข้อมูลในต้นไม้: อาร์กิวเมนต์: root, d ส่วนตัวของฟังก์ชัน: รันลูป for จนกว่า temp จะชี้ไป NULL หรือพบข้อมูล ถ้า d < tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกซ้าย ถ้า d > tmp->data ย้ายพอยน์เตอร์ tmp ไปลูกขวา ถ้า d = tmp->data พิมพ์ว่าพบข้อมูลและจำนวนนับ แล้วคืนค่าไป main มิฉะนั้น พิมพ์ว่าไม่พบข้อมูล จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; struct nod //ประกาศโหนด { int data; int cnt; nod *l; nod *r; }; nod* CreateNod(int d) //สร้างโหนดใหม่ { nod *newnod = new nod; newnod->data = d; newnod->cnt = 1; newnod->l= NULL; newnod->r = NULL; return newnod; } nod* Insert(nod* root, int d) //แทรกข้อมูล { nod *tmp = CreateNod(d); nod *t = new nod; t = root; if(root == NULL) root = tmp; else { while(t != NULL) { if(t->data == d) { t->cnt++; break; } else if(t->data < d ) { if(t->r== NULL) { t->r= tmp; break; } t = t->r; } else if(t->data > d) { if(t->l== NULL) { t->l= tmp; break; } t = t->l; } } } return root; } void SearchNode(nod *root, int d) //ค้นหาข้อมูล { nod *tmp = new nod; tmp = root; while(tmp != NULL) { if(tmp->data == d) { cout<<"\nData item "<<d<<" is present "<<tmp->cnt<<" number of times."; return; } else if(tmp->data > d) tmp = tmp->l; else tmp = tmp->r; } cout<<"\n Data not found"; return; } int main() { char c; int n, i, a[20] = {8,1,3,6,4,7,10,14,13,7,6,1,26,4,26,20,21,12,10,1}; //องค์ประกอบอาร์เรย์ nod *root = new nod; root = NULL; for(i = 0; i < 20; i++) root = Insert(root, a[i]); up: cout<<"\nEnter the Element to be searched: "; cin>>n; SearchNode(root, n); cout<<"\n\nWant to search more...enter choice(y/n)?"; cin>>c; if(c == 'Y' || c == 'y') goto up; return 0; }
ผลลัพธ์
Enter the Element to be searched: 7 Data item 7 is present 2 number of times. Want to search more...enter choice(y/n)?y Enter the Element to be searched: 6 Data item 6 is present 2 number of times. Want to search more...enter choice(y/n)?y Enter the Element to be searched: 4 Data item 4 is present 2 number of times. Want to search more...enter choice(y/n)?y Enter the Element to be searched: 15 Data not found Want to search more...enter choice(y/n)?n
