Using C11 1 Measure elapsed time of searching for an element

Using C++11

(1) Measure elapsed time of searching for an element in a binary tree for multiple sizes of the tree.

(2) Use at least 50 points of N to draw the graph

(3) Does the graph agree with the theoretical complexity? Why?

(4) For extra credit, use random seeds based on the timer and average elapsed time per each tree size

Solution

Code:

#include<iostream>
#include<conio.h>
#include<process.h>
#include<time.h>
#include <tchar.h>
#include <windows.h>
__int64 ctr11 = 0, ctr22 = 0, freqq = 0;
using namespace std;
int count=0;
struct bina_node
{
int dat_val;
bina_node *lft;
bina_node *rght;
};
class bina_tree
{
public:
bina_tree();

void insert_binatree(int val);
bina_node *search_binatree(int val);

private:
void insert_binatree(int val, bina_node *leaf);
bina_node *search_binatree(int val, bina_node *leaf);
  
bina_node *root;
};
bina_tree::bina_tree()
{
root=NULL;
}
void bina_tree::insert_binatree(int val)
{

if(root!=NULL)
insert_binatree(val, root);
else
{
root=new bina_node;
root->dat_val=val;
root->lft=NULL;
root->rght=NULL;
}
}
void bina_tree::insert_binatree(int val, bina_node *leaf)
{
if(val< leaf->dat_val)
{
if(leaf->lft!=NULL)
insert_binatree(val, leaf->lft);
else
{
leaf->lft=new bina_node;
leaf->lft->dat_val=val;
leaf->lft->lft=NULL;
leaf->lft->rght=NULL;   
}
}
else if(val>=leaf->dat_val)
{
if(leaf->rght!=NULL)
insert_binatree(val, leaf->rght);
else
{
leaf->rght=new bina_node;
leaf->rght->dat_val=val;
leaf->rght->lft=NULL;
leaf->rght->rght=NULL;
}
}
}
bina_node *bina_tree::search_binatree(int val)
{
return search_binatree(val, root);
}
bina_node *bina_tree::search_binatree(int val, bina_node *leaf)
{
   count++;
if(leaf!=NULL)
{
if(val==leaf->dat_val)
return leaf;
if(val<leaf->dat_val)
return search_binatree(val, leaf->lft);
else
return search_binatree(val, leaf->rght);
}
else return NULL;
}
int main()
{
   clock_t Start, Stop;
   double Sec;
   srand (time(0));
   for(int i=0;i<50;i++)
   {
  
   int size=rand()%100;
   bina_tree b;
   for(int k=0;k<size;k++)
   {
  
   b.insert_binatree(rand()%200);
   }
  
   QueryPerformanceCounter((LARGE_INTEGER *)&ctr11);
b.search_binatree(rand()%200);
   QueryPerformanceCounter((LARGE_INTEGER *)&ctr22);

   QueryPerformanceFrequency((LARGE_INTEGER *)&freqq);
  
   cout<<\"Time taken for search_binatree of size \"<<size<<\": \"<<(ctr22 - ctr11) * 1.0 / freqq<<endl;
   cout<<count<<endl;
   }
  
   system(\"pause\");
   return 0;
}