이진 검색 방식을 사용하여 주어진 숫자의 발생 횟수를 찾는 C++ 프로그램입니다.
알고리즘
Begin function Insert() to insert nodes into the tree: Arguments: root, d. Body of the function: Create node using data from argument list. If tree is completely empty, then insert new node as root. If d = tmp->data, increase the count of that particular node. If d < tmp->data, move the tmp pointer to the left child. If d > tmp->data, move the tmp pointer to the right child. End Begin function SearchNode() to search item in the tree: Arguments: root, d. Body of the function: Run the for loop until temp points to a NULL pointer or data item is found. If d < tmp->data, move the tmp pointer to the left child. If d > tmp->data, move the tmp pointer to the right child. If d = tmp->data, print the item found and it’s count and then return to main. Else Print data not found. End
예시
#include<iostream> using namespace std; struct nod //declaration of node { int data; int cnt; nod *l; nod *r; }; nod* CreateNod(int d) //creation of new node { nod *newnod = new nod; newnod->data = d; newnod->cnt = 1; newnod->l= NULL; newnod->r = NULL; return newnod; } nod* Insert(nod* root, int d) //perform insertion { 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) //perform searching { 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}; //take the elements of the array 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