C program Heap and Tree Complete the implementation of the BST bag. There are 6
ID: 665815 • Letter: C
Question
C program
Heap and Tree
Complete the implementation of the BST bag. There are 6 functions to implement:
_createNode
_heightOfSubTree
_addNodeToSubTree
_containsSubTree
_removeLeftMost
_removeNodeFromSubtree
Note that these functions are all private (note the _), and that the public functions which call the private functions have all been written for you.
None of these functions are particularly long, but they can be a bit time consuming to write since they often use recursion to traverse down the tree to an area of interest, then assign returned pointers as function calls return in order to put the tree back together.
FILES YOU WILL NEED:
//BST.h
//BST.c
//type.h
//main.c
ERRATA
The makefile does not link the C library math.h properly, change the lines that read
To read as follows
Note the addition of -lm.
Delete the following lines from main.c:
Explanation / Answer
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
void deleteFromTree( struct node **nodeToDelete )
{
struct node* tempNode = NULL;
struct node* currentNode = *nodeToDelete;
struct node* trailNode = NULL;
if( (*nodeToDelete)->leftChild == NULL && (*nodeToDelete)->rightChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = NULL;
free( tempNode );
}
else if( (*nodeToDelete)->leftChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = (*nodeToDelete)->rightChild;
free( tempNode );
}
else if( (*nodeToDelete)->rightChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = (*nodeToDelete)->leftChild;
free( tempNode );
}
else
{
currentNode = currentNode->leftChild;
while( currentNode != NULL )
{
trailNode = currentNode;
currentNode = currentNode->rightChild;
}
(*nodeToDelete)->data = trailNode->data;
tempNode = trailNode;
trailNode = trailNode->leftChild;
free(tempNode);
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.