二分探索アプローチを使用して特定の数の出現数を見つけるC++プログラム

これは、バイナリ検索アプローチを使用して特定の数の出現回数を見つける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