Please code in C Create a C program called rec9.c that has several additions to
ID: 3860048 • Letter: P
Question
Please code in C
Create a C program called rec9.c that has several additions to the binary tree code
First, add an argument called direction to both the searchBT and insertBT functions.
NodeT *searchBT(NodeT *pRoot, int iMatch, int direction)
NodeT *insertBT(NodeT **ppRoot, int iMatch, int direction)
Then, update the inside of the functions to use this new argument to allow the binary trees to be sorted in ascending or descending order. For example, if direction == -1, the tree is in descending order and if direction == 1, the tree is in ascending order.
After this, make a new version of each function (search and insert) that works on strings instead of integers. Add another field to your NodeT structure to hold the string in each node of the tree.
In your main function, create four different trees
int, ascending order
int, descending order
string, ascending order
string, descending order
Explanation / Answer
The code is modified according to the requirements of the question and some simple searches are done on diffferent trees to demonstrate the building of the trees and search through them.
Please don't forget to rate the answer if it helped. Thank you.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct NodeT
{
int iInfo; // info might be several attributes or just one
char sName[15]; // string data in the node
struct NodeT *pLeft;
struct NodeT *pRight;
} NodeT;
/* Binary Rearch through Binary Tree, starting from root
node looking for matching node.
Return NULL if arriving at end node with no branches,
otherwise return pointer to matching node.
Essentially the same idea as Binary Search thru sorted
array. log2(N) running time for worst case.
*/
NodeT *searchBT(NodeT *pRoot, int iMatch, int direction)
{
NodeT *p = pRoot;
// iterative algorithm
while (p != NULL)
{
if (iMatch == p->iInfo)
{
break;
}
else if (iMatch < p->iInfo)
{
if(direction == 1) //ascending order
p = p->pLeft; //go left branch
else // descending order
p = p->pRight;
}
else
{
if(direction == 1) //ascending order
p = p->pRight; //go right branch
else //descending order
p = p->pLeft;
}
} // end while
// at this point, if p is NULL, iMatch wasn't found
return p;
}
/* inserts new node based upon sort order(Ascending) of BT.
return pointer to new node.
*/
NodeT *insertBT(NodeT **ppRoot, int iNewInfo, int direction)
{
NodeT *pNew;
NodeT *pParent = NULL;
NodeT *p = *ppRoot;
pNew = (NodeT *)malloc(sizeof(NodeT)); //(Node *) casts memory from malloc
pNew->iInfo = iNewInfo; //store new info into new node
pNew->pLeft = pNew->pRight = NULL;
pNew->sName[0] = ''; //no string data in the node
//insert node
if(*ppRoot == NULL) { //special case, Tree is empty
*ppRoot = pNew; //insert first node into tree
}
else { //normal case: tree already as root node
while (p != NULL) // iterative algorithm
{
pParent = p;
if (iNewInfo < p->iInfo)
{
if(direction == 1)
p = p->pLeft; //go left branch
else
p = p->pRight;
}
else
{
if(direction == 1)
p = p->pRight; //go right branch
else
p = p->pLeft;
}
} // end while
//parent node located, insert new node on left or right branch
if(iNewInfo < pParent->iInfo)
{
if(direction == 1)
pParent->pLeft = pNew;
else
pParent->pRight = pNew;
}
else
{
if(direction == 1)
pParent->pRight = pNew;
else
pParent->pLeft = pNew;
}
}
//return pointer to inserted node
return pNew;
}
/* Binary Search through Binary Tree, starting from root
node looking for matching node.
Return NULL if arriving at end node with no branches,
otherwise return pointer to matching node.
Essentially the same idea as Binary Search thru sorted
array. log2(N) running time for worst case.
*/
NodeT *searchStringBT(NodeT *pRoot, char* sMatch, int direction)
{
NodeT *p = pRoot;
// iterative algorithm
while (p != NULL)
{
if (strcmp(sMatch, p->sName) == 0)
{
break;
}
else if (strcmp(sMatch, p->sName) < 0)
{
if(direction == 1) //ascending order
p = p->pLeft; //go left branch
else // descending order
p = p->pRight;
}
else
{
if(direction == 1) //ascending order
p = p->pRight; //go right branch
else //descending order
p = p->pLeft;
}
} // end while
// at this point, if p is NULL, iMatch wasn't found
return p;
}
/* inserts new node based upon sort order(Ascending) of BT.
return pointer to new node.
*/
NodeT *insertStringBT(NodeT **ppRoot, char * sNewInfo, int direction)
{
NodeT *pNew;
NodeT *pParent = NULL;
NodeT *p = *ppRoot;
pNew = (NodeT *)malloc(sizeof(NodeT)); //(Node *) casts memory from malloc
strcpy(pNew->sName, sNewInfo); //store new info into new node
pNew->iInfo = 0; //no int data
pNew->pLeft = pNew->pRight = NULL;
//insert node
if(*ppRoot == NULL) { //special case, Tree is empty
*ppRoot = pNew; //insert first node into tree
}
else { //normal case: tree already as root node
while (p != NULL) // iterative algorithm
{
pParent = p;
if (strcmp(sNewInfo, p->sName) < 0)
{
if(direction == 1)
p = p->pLeft; //go left branch
else
p = p->pRight;
}
else
{
if(direction == 1)
p = p->pRight; //go right branch
else
p = p->pLeft;
}
} // end while
//parent node located, insert new node on left or right branch
if(strcmp(sNewInfo, pParent->sName) < 0)
{
if(direction == 1)
pParent->pLeft = pNew;
else
pParent->pRight = pNew;
}
else
{
if(direction == 1)
pParent->pRight = pNew;
else
pParent->pLeft = pNew;
}
}
//return pointer to inserted node
return pNew;
}
int main(int argc, char *argv[])
{
int i;
int count = 8;
int numbers[8] = {5, 3, 8 , 1, 4, 6, 2, 7};
char fruits[8][15] = {"orange", "mango", "apple", "grapes", "banana", "pear", "strawberry", "pineapple"};
//roots for 4 trees, numbers ascending, numbers descending, strings ascending, string descending
NodeT *numAsc = NULL;
NodeT *numDesc = NULL;
NodeT *strAsc = NULL;
NodeT *strDesc = NULL;
NodeT *search = NULL;
//create the 4 trees by inserting the numbers and string from the above array
for(i = 0; i < count; i++)
{
insertBT(&numAsc, numbers[i], 1); // add the number to ascending number tree
insertBT(&numDesc, numbers[i], -1); //add the number to descending number tree
insertStringBT(&strAsc, fruits[i], 1); // add the fruit name to string ascending tree
insertStringBT(&strDesc, fruits[i], -1); // add the fruit name to string descending tree
}
//search for numbers
search = searchBT(numAsc, 4, 1);
if(search == NULL)
printf("4 is not found in numbers ascending tree ");
else
printf("4 is found in numbers ascending tree ");
search = searchBT(numDesc, 9, 1);
if(search == NULL)
printf("9 is not found in numbers descending tree ");
else
printf("9 is found in numbers descending tree ");
//search for strings
search = searchStringBT(strAsc, "grapes", 1);
if(search == NULL)
printf("grapes is not found in strings ascending tree ");
else
printf("grapes is found in strings ascending tree ");
search = searchStringBT(strDesc, "guava", 1);
if(search == NULL)
printf("guava is not found in strings descending tree ");
else
printf("guava is found in strings descending tree ");
}
output
4 is found in numbers ascending tree
9 is not found in numbers descending tree
grapes is found in strings ascending tree
guava is not found in strings descending tree