Chương trình C ++ để Tìm số lần xuất hiện của một Số nhất định bằng cách sử dụng phương pháp Tìm kiếm nhị phân

Đây là một chương trình C ++ để tìm số lần xuất hiện của một số nhất định bằng cách sử dụng phương pháp Tìm kiếm nhị phân.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

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