2. Verifying Binary Search Tree Performance (30 pts) Build 10 binary search tree

Question

2. Verifying Binary Search Tree Performance (30 pts)
Build 10 binary search trees of different sizes and compute an average # of
comparisons when using those trees to search for random keys.
You will need to write a C program to do this. Use the search and insertion algorithm on
page 404: q = NULL;
      p = tree; /* tree can also be interpreted as the "root" */
      while (p != NULL){
       if (key == k(p)){
           return p;
       }
       q = p;
       if (key < k(p)){
           p = left(p);
       }
       else {
           p = right(p);
       }
      } /* end while */
      v = maketree(rec, key);
      if (q == NULL){
       tree = v;
      }
      else {
       if (key < k(q)){
           left(q) = v;
       }
       else {
           right(q) = v;
       }
      return(v);   from Data Structures Using C And C++ 2nd edition
                        Langsam, Augenstein, Tenenbaum
  

to build 10 trees of different sizes (see below). Use the provided data files to
populate your trees. For example, datafile_10.txt has the data for you to insert into your
10 node tree, and datafile_100.txt has the data for you to insert into your 100 node tree.
Once each tree has been built, test the tree

Explanation / Answer

#include<iostream.h>
#include<conio.h>


class BSTNode
{
int data;
BSTNode *p,*lc,*rc;
public :
BSTNode()
{
data=0;
p=NULL;
lc=NULL;
rc=NULL;
}

BSTNode(int k)
{
data=k;
p=NULL;
lc=NULL;
rc=NULL;
}

void setData(int k){data=k;}
int getData(){return data;}

void setP(BSTNode *n){p=n;}
BSTNode* getP(){return p;}

void setLc(BSTNode *n){lc=n;}
BSTNode* getLc(){return lc;}

void setRc(BSTNode *n){rc=n;}
BSTNode* getRc(){return rc;}

};

class BST
{
BSTNode *root;
public :

BST();
BSTNode* getRoot();
void addNode(BSTNode *n);
void preorder(BSTNode *ptr);
void inorder(BSTNode *ptr);
void postorder(BSTNode *ptr);
BSTNode* search(int data);
BSTNode* treeMin(BSTNode *ptr);
BSTNode* treeMax(BSTNode *ptr);
BSTNode* sucessor(BSTNode *ptr);
BSTNode* deleteNode(BSTNode *z);
};


BSTNode* BST :: deleteNode(BSTNode *z)
{
BSTNode *y,*x;
if(z->getLc()==NULL || z->getRc()==NULL)
   y=z;
else
   y=sucessor(z);

if(y->getLc()!=NULL)
   x=y->getLc();
else
   x=y->getRc();

if(x!=NULL)
   x->setP(y);

if(y==root)
    root=x;
else
   {
    x->setP(y->getP());
    if(y==y->getP()->getLc())
     y->getP()->setLc(x);
    else
     y->getP()->setRc(x);
   }

if(y!=z)
z->setData(y->getData());
return y;
   }






BST :: BST()
{
   root=NULL;
}

BSTNode* BST :: getRoot()
{
return root;
}

void BST :: addNode(BSTNode *n)
{
int data;
cout<<" Enter the data : ";
cin>>data;
n->setData(data);

BSTNode *ptr=root;
BSTNode *parent;
if(ptr==NULL)
   {
    root=n;
   }
else
   {
    while(ptr!=NULL)
     {
      parent=ptr;
      if(n->getData()<ptr->getData())
       ptr=ptr->getLc();
      else
       ptr=ptr->getRc();
     }
    n->setP(parent);

    if(parent->getData()>n->getData())
     parent->setLc(n);
    else
     parent->setRc(n);
   }
}


BSTNode* BST :: treeMin(BSTNode *ptr)
{
   while(ptr->getLc()!=NULL)
    ptr=ptr->getLc();

   return ptr;
}
BSTNode* BST :: treeMax(BSTNode *ptr)
{
   while(ptr->getRc()!=NULL)
    ptr=ptr->getRc();

return ptr;
}




void BST :: preorder(BSTNode *ptr)
{
if(ptr!=NULL)
   {
    cout<<ptr->getData()<<"   ";
    preorder(ptr->getLc());
    preorder(ptr->getRc());
   }

}

void BST :: inorder (BSTNode *ptr)
{
if(ptr!=NULL)
   {
    inorder(ptr->getLc());
    cout<<ptr->getData()<<"   ";
    inorder(ptr->getRc());
   }

}

void BST :: postorder(BSTNode *ptr)
{
if(ptr!=NULL)
   {
    postorder(ptr->getLc());
    postorder(ptr->getRc());
    cout<<ptr->getData()<<"   ";
   }

}


BSTNode* BST :: search(int data)
{
BSTNode *ptr=root;
while(ptr!=NULL && ptr->getData()!=data)
   {
    if(data<ptr->getData())
     ptr=ptr->getLc();
    else
     ptr=ptr->getRc();

   }
return ptr;
}



BSTNode* BST :: sucessor(BSTNode *ptr)
{
if(ptr!=NULL && ptr->getRc()!=NULL)
   return treeMin(ptr->getRc());

BSTNode *parent=ptr->getP();
while(parent!=NULL && parent->getRc()==ptr)
   {
    ptr=parent;
    parent=parent->getP();

   }


return parent;
}



void main()
{
int choice;
BST b;
clrscr();
do
   {
    clrscr();
    cout<<" 1 ---Enter the node";
    cout<<" 2 ---PreOrder 3 ---InOrder 4 ---PostOrder";
    cout<<" 5 ---Search";
    cout<<" 6 ---Tree min 7 ---Tree max";
    cout<<" 8 ---sucessor";
    cout<<" 10---Delete a node";
    cout<<" 11---Exit";
    cout<<" Enter the choice : ";
    cin>>choice;

    if(choice==1)
     {
       BSTNode *node=new BSTNode();
       b.addNode(node);
     }

    if(choice==2)
     {
      cout<<" PreOrder of Graph : ";
      b.preorder(b.getRoot());
      getch();
     }

    if(choice==3)
     {
      cout<<" InOrder of Graph : ";
      b.inorder(b.getRoot());
      getch();
     }

    if(choice==4)
     {
      cout<<" PostOrder of Graph : ";
      b.postorder(b.getRoot());
      getch();
     }


    if(choice==5)
     {
      int data;
      BSTNode *search;
      cout<<" Enter the searching element : ";
      cin>>data;
      search=b.search(data);
      if(search->getData()==data)
       cout<<" Data found";
      else
       cout<<" Data not found";

      getch();
     }

    if(choice==6)
     {
      cout<<" Tree Minimum : "<<b.treeMin(b.getRoot())->getData();
      getch();
     }
    if(choice==7)
     {
      cout<<" Tree Maximum : "<<b.treeMax(b.getRoot())->getData();
      getch();
     }



    if(choice==8)
     {
      int data;
      BSTNode *search;
      BSTNode *suc;
      cout<<" Enter the data : ";
      cin>>data;
      search=b.search(data);
      if(search->getData()==data)
       {
    suc=b.sucessor(search);
    cout<<" Sucessor of "<<data <<" : " <<suc->getData();
       }
      else
       {
    cout<<" Data not found";
       }
      getch();
     }

    if(choice==10)
     {
      int data;
      cout<<"Enter the deleting node : ";
      cin>>data;
      BSTNode *search=b.search(data);

      if(search->getData()!=data)
    cout<<" Data not found ";
      else
       {
    BSTNode *del=b.deleteNode(search);
    cout<<"Node "<<del->getData()<<" is deleated.";
       }

      getch();
     }


   }while(choice!=11);

}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.