C++ BINARY TREE CLASS The BinaryTree.h file wll contain your class specification

Question

C++

BINARY TREE CLASS The BinaryTree.h file wll contain your class specification for class named BinaryTree, which is an implementation of a Binary Search Tree. The BinaryTree.cpp file wil contain your class implementation for the BinaryTree class. ATTRIBUTES Instead of each tree node containing one value, your tree nodes will contain TWwO values (in addition to the left & right pointers): A string containine the name of a customer An integer containing the number of Krabby Patties the customer ate 2. You will also need a pointer to the root of the tree. CONSTRUCTOR & DESTRUCTOR You need a constructor which will set the root pointer to NULL. You will also need a destructor, which will call a private function named destroySubTree. The destroySubTree function should delete all nodes in the tree since they were dynamically allocated. BINARY TREE OPERATIONS: a new node (requires two functions) a. The public function (insertNode) should accept a new customers name and the number of Krabby Patties they ate. 1. This function should create a new TreeNode and fill it with these new values and then call the private function (insert) The insert function (recursive function) inserts the node in the correct position. b. 2. Delete a node (requires three functions) a. The public function (remove) accepts a customer's name in order to identify the node that should be removed This function prints, "You are trying to delete [namel." This function will call the private deleteNode function (a recursive function). The deleteNode function tries to find the node that needs deleted. If deleteNode finds the node, It calls the private makeDeletion function. If deleteNode does not find the node, it should print "I'm sorry. That customer can't be found in the Krusty Krab." b. c. The makeDeletion function removes the node and reattaches the branches of the tree below the node 3. (requires two functions) The public function (displaylnOrder) will call the private overloaded function also called displayinOrden The private displaylnOrder accepts a TreeNode as an argument and it is a recursive function which traverses the nodes using the inorder method and prints the customer's name from each node a. b. 4. The searchNode function accepts the customer's name as an argument and then it will look at each node (traverse the tree) to find the node with that name. If the name is found, the function returns the number of Krabby Patties that customer ate. If not, then it will return -1 instead. a. 5. Find the lowest number of Krabby Patties eaten by any customer (requires two functions] The public function (getLeastNumPatties) accepts two arguments-a string that will eventually hold the customer's name that has the least number of eaten Krabby Patties and an integer that will eventually hold the customer's # of eaten Krabby Patties. This function sets the integer parameter (leastPatties) to the root node's # of patties and then calls the private function (getLeast). The getleast function is a recursive function that traverses the nodes like the displaylnOrder function except instead of printing out the customer's name, it will check to see if the current node has a smaller number then the one saved in the leastPatties variable. If so, then save this node's customer name & number of patties as the new least. a. b. 6. number of Krabby Patties eaten by any customer (requires two functions) a. Follow the Instructions for finding the lowest except find the highest instead number of Krabby Patties eaten by ALL customers (requires two functions) The public function (eetTotalNumPatties) accepts no arguments. It reates a variable to hold the total and then calls the private getTotal function, sending the root node & the total variable (send total by reference) to the function. Then, this function will return the total as an integer The getTotal function is a recursive function that traverses the tree like the displaylnOrder function except Instead of printing out the customer's name, it will get a running total of Krabby Patties eaten from each node. a. b.

Explanation / Answer

Source Code

#include<stdio.h>
#include<alloc.h>
#include<conio.h>
struct tree
{
char custName[50];

int KPate;
struct tree *l;
struct tree *r;
};

struct tree *insert(struct tree *,int);
void inorder(struct tree *);
struct tree *delet(struct tree *,int);
struct tree *search(struct tree *);
int main(void)
{

struct tree *root;
int ch,ate_no;

char Name[50]
root = NULL;
clrscr();
/* rear = NULL;*/
do
{
do
{
   printf(" 1. Insert in Binary Tree ");
   printf(" 2. Delete from Binary Tree ");
   printf(" 3. Inorder traversal of Binary tree");
   printf(" 4. Search and replace ");
   printf(" 5. Exit ");
   printf(" Enter ch : ");
   scanf(" %d",&ch);
   if(ch<1 || ch>7)
      printf(" Invalid ch - try again");
}while (ch<1 || ch>7);
switch(ch)
{
   case 1:
printf(" Enter new customer: ");
scanf("%s", &name);

printf("Enter krabby Patties ate=");

scanf("%d",&ate_no);
root= insert(root,name,ate_no);
printf(" root is %d",root->custName);
printf(" Inorder traversal of binary tree is : ");
inorder(root);
break;
   case 2:
printf(" Enter the customer name to be deleted : ");
scanf(" %s",&name);
root=delet(root,name);
inorder(root);
break;
   case 3:
printf(" Inorder traversal of binary tree is : ");
inorder(root);
break;
   case 4:
printf(" Search and replace operation in binary tree ");
root=search(root);
break;
   default:
printf(" End of program ");
   } /* end of switch */
}while(ch !=5);
return(0);
}

struct tree *insert(struct tree *root, char name[], int ate)
{
if(!root)
{
    root=(struct tree*)malloc(sizeof(struct tree));
    root->custName = name;

    root->KPate= ate;
    root->l = NULL;
    root->r = NULL;
    return(root);
}
if(root->custName > x)
     root->l = insert(root->l,x);
else
   {
     if(root->data < x)
root->r = insert(root->r,x);
   }
   return(root);
}


void inorder(struct tree *root)
{
    if(root != NULL)
   {
     inorder(root->l);
     printf(" %d",root->custName);
     inorder(root->r);
   }
   return;
}

/* FUNCTION TO DELETE A NODE FROM A BINARY TREE */
struct tree *delet(struct tree *ptr,char name[50])
{
struct tree *p1,*p2;
if(!ptr)
{
    printf(" Node not found ");
    return(ptr);
}
else
{
     if(ptr->custName <name)
     {
      ptr->r = delet(ptr->r,name);
      /*return(ptr);*/
     }
     else if (ptr->custName >name)
      {
       ptr->l=delet(ptr->l,x);
       return ptr;
      }
      else                     /* no. 2 else */
       {
if(ptr->data == x)    /* no. 2 if */
{
if(ptr->l == ptr->r) /*i.e., a leaf node*/
{
   free(ptr);
   return(NULL);
}
else if(ptr->l==NULL) /* a r subtree */
{
p1=ptr->r;
free(ptr);
return p1;
}
else if(ptr->r==NULL)   /* a l subtree */
{
p1=ptr->l;
free(ptr);
return p1;
}
else
{
p1=ptr->r;
p2=ptr->r;
while(p1->l != NULL)
   p1=p1->l;
p1->l=ptr->l;
free(ptr);
return p2;
}
      }/*end of no. 2 if */
     }/* end of no. 2 else */
/* check which path to search for a given no. */
}
return(ptr);
}
/* function to search and replace an element in the binary tree */
struct tree *search(struct tree *root)
{
int no,i,ino;
struct tree *ptr;
ptr=root;
printf(" Enter the element to be searched :");
scanf(" %d",&no);
fflush(stdin);
while(ptr)
{
if(no>ptr->data)
     ptr=ptr->r;
else if(no<ptr->data)
     ptr=ptr->l;
else
     break;
}
if(ptr)
{
printf(" Element %d which was searched is found and is = %d",no,ptr->data);
printf(" Do you want replace it, press 1 for yes : ");
scanf(" %d",&i);
if(i==1)
{
   printf(" Enter new element :");
   scanf(" %d",&ino);
   ptr->data=ino;
}
else
    printf(" It's okay");
}
else
   printf(" Element %d does not exist in the binary tree",no);
return(root);
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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