Question: bst.zip contains a student's submission for CS261's binary search tree assignment. The main.c file contains some test cases. Your task is to: (1) Edit the
bst.zip contains a student's submission for CS261's binary search tree assignment. The main.c file contains some test cases. Your task is to: (1) Edit the makefile so that Gcov can be run on the source code. (2) Use Gcov to check how well bst.c was tested and provide the percentage of lines executed (do not put % in your answer).
makefile
default: prog
prog:
gcc -Wall -std=c99 -o prog compare.c bst.c main.c
clean:
rm prog
cleanall:
rm prog
bst.c
/*
File: bst.c
Implementation of the binary search tree data structure.
*/
#include
#include
#include "assert.h"
#include "bst.h"
struct Node {
TYPE val;
struct Node *left;
struct Node *right;
};
struct BSTree {
struct Node *root;
int cnt;
};
/*----------------------------------------------------------------------------*/
void initBSTree(struct BSTree *tree)
{
tree->cnt = 0;
tree->root = 0;
}
struct BSTree* newBSTree()
{
struct BSTree *tree = (struct BSTree *)malloc(sizeof(struct BSTree));
assert(tree != 0);
initBSTree(tree);
return tree;
}
/*----------------------------------------------------------------------------*/
void _freeBST(struct Node *node)
{
if (node != 0) {
_freeBST(node->left);
_freeBST(node->right);
free(node);
}
}
void clearBSTree(struct BSTree *tree)
{
_freeBST(tree->root);
tree->root = 0;
tree->cnt = 0;
}
void deleteBSTree(struct BSTree *tree)
{
clearBSTree(tree);
free(tree);
}
/*----------------------------------------------------------------------------*/
int isEmptyBSTree(struct BSTree *tree) { return (tree->cnt == 0); }
int sizeBSTree(struct BSTree *tree) { return tree->cnt; }
/*----------------------------------------------------------------------------*/
struct Node *_addNode(struct Node *cur, TYPE val)
{
/*write this*/
/* return NULL; */
struct Node *newnode;
/* case1 - cur is null */
if (cur == NULL)
{ /*create new node and return*/
newnode = (struct Node *)malloc(sizeof(struct Node));
assert(newnode != 0);
newnode->val = val;
/*newnode->val->number = val->number;*/
newnode->left = newnode->right = 0;
return newnode;
}
if (EQ(compare(val,cur->val),-1))
{
cur->left = _addNode(cur->left,val);
}
else if (EQ(compare(val, cur->val),1))
{
cur->right = _addNode(cur->right, val);
}
return cur;
}
void addBSTree(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}
/*----------------------------------------------------------------------------*/
int containsBSTree(struct BSTree *tree, TYPE val)
{
/*write this*/
/* return 0; */
struct Node *cur = tree->root;
while (cur != 0) {
if (EQ(compare(val,cur->val),0))
return 1; /* Return true if val found. */
if (EQ(compare(val, cur->val),-1))
cur = cur->left; /* Otherwise, go to the left */
else cur = cur->right; /* or right, depending on val. */
}
return 0;
}
/*----------------------------------------------------------------------------*/
TYPE _leftMost(struct Node *cur)
{
/*write this*/
/*return NULL;*/
while (cur->left != 0)
cur = cur->left;
return cur->val;
}
/*----------------------------------------------------------------------------*/
struct Node *_removeLeftMost(struct Node *cur)
{
/*write this*/
/* return NULL;*/
struct Node *node;
if (cur->left != 0) {
cur->left = _removeLeftMost(cur->left);
return cur;
}
node = cur->right;
free(cur);
return node;
}
/*----------------------------------------------------------------------------*/
struct Node *_removeNode(struct Node *cur, TYPE val)
{
/*write this*/
/* return NULL; */
struct Node *temp;
if (EQ(compare(val, cur->val),0)) { /* Found val. */
if (cur->right == 0) {
temp = cur->left;
free(cur);
return temp;
}
cur->val = _leftMost(cur->right);
cur->right = _removeLeftMost(cur->right);
}
else if (EQ(compare(val, cur->val),-1))
cur->left = _removeNode(cur->left, val);
else
cur->right = _removeNode(cur->right,val);
return cur;
}
void removeBSTree(struct BSTree *tree, TYPE val)
{
if (containsBSTree(tree, val)) {
tree->root = _removeNode(tree->root, val);
tree->cnt--;
}
}
/*----------------------------------------------------------------------------*/
/* The following is used only for debugging, set to "#if 0" when used
in other applications */
#if 1
#include
/*----------------------------------------------------------------------------*/
void printNode(struct Node *cur) {
if (cur == 0) return;
printf("(");
printNode(cur->left);
/*Call print_type which prints the value of the TYPE*/
print_type(cur->val);
printNode(cur->right);
printf(")");
}
void printTree(struct BSTree *tree) {
if (tree == 0) return;
printNode(tree->root);
}
/*----------------------------------------------------------------------------*/
#endif
bst.h
/* File: bst.h Interface definition of the binary search tree data structure. */
#ifndef __BST_H #define __BST_H
# ifndef LT # define LT(A, B) ((A) < (B)) # endif
# ifndef EQ /*Modify this to an epsilon test for better accuracy*/ # define EQ(A, B) ((A) == (B)) # endif
/* Defines the type to be stored in the data structure. These macros * are for convenience to avoid having to search and replace/dup code * when you want to build a structure of doubles as opposed to ints * for example. */
# ifndef TYPE # define TYPE void* # endif
/* function used to compare two TYPE values to each other, define this in your compare.c file */ int compare(TYPE left, TYPE right); /* function used to print TYPE values, define this in your compare.c file */ void print_type(TYPE curval);
struct BSTree; /* Declared in the c source file to hide the structure members from the user. */
/* Initialize binary search tree structure. */ void initBSTree(struct BSTree *tree);
/* Alocate and initialize search tree structure. */ struct BSTree *newBSTree();
/* Deallocate nodes in BST. */ void clearBSTree(struct BSTree *tree);
/* Deallocate nodes in BST and deallocate the BST structure. */ void deleteBSTree(struct BSTree *tree);
/*-- BST Bag interface --*/ int isEmptyBSTree(struct BSTree *tree); int sizeBSTree(struct BSTree *tree);
void addBSTree(struct BSTree *tree, TYPE val); int containsBSTree(struct BSTree *tree, TYPE val); void removeBSTree(struct BSTree *tree, TYPE val); void printTree(struct BSTree *tree); # endif
compare.c
#include
#include "bst.h"
#include "assert.h"
#include "structs.h"
/*----------------------------------------------------------------------------
very similar to the compareTo method in java or the strcmp function in c. it
returns an integer to tell you if the left value is greater then, less then, or
equal to the right value. you are comparing the number variable, letter is not
used in the comparison.
if left < right return -1
if left > right return 1
if left = right return 0
*/
/*Define this function type casting the value of void * to the desired type*/
int compare(TYPE left, TYPE right)
{
/*write this*/
/*return 0;*/
struct data* data1;
struct data* data2;
data1=(struct data*)left;
data2=(struct data*)right;
if (data1->number < data2->number)
return -1;
else if (data1->number > data2->number)
return 1;
else
return 0;
}
/*Define this function type casting the value of void * to the desired type*/
void print_type(TYPE curval)
{
/*write this*/
/*return 0;*/
struct data* data1;
data1=(struct data*)curval;
printf(" %d ", data1->number);
}
main.c
#include
#include
#include "bst.h"
#include "structs.h"
/* Example main file to begin exercising your tree */
/*
Functions to test
struct Node *_addNode(struct Node *cur, TYPE val)
int containsBSTree(struct BSTree *tree, TYPE val)
TYPE _leftMost(struct Node *cur)
struct Node *_removeLeftMost(struct Node *cur)
struct Node *_removeNode(struct Node *cur, TYPE val)
*/
struct Node {
TYPE val;
struct Node *left;
struct Node *right;
};
struct BSTree {
struct Node *root;
int cnt;
};
TYPE _leftMost(struct Node *cur);
struct Node *_removeLeftMost(struct Node *cur);
struct Node *_removeNode(struct Node *cur, TYPE val);
struct BSTree *buildBSTTree() {
/* 50
13 110
10
*/
struct BSTree *tree = newBSTree();
/*Create value of the type of data that you want to store*/
struct data *myData1 = (struct data *) malloc(sizeof(struct data));
struct data *myData2 = (struct data *) malloc(sizeof(struct data));
struct data *myData3 = (struct data *) malloc(sizeof(struct data));
struct data *myData4 = (struct data *) malloc(sizeof(struct data));
myData1->number = 50;
myData1->name = "rooty";
myData2->number = 13;
myData2->name = "lefty";
myData3->number = 110;
myData3->name = "righty";
myData4->number = 10;
myData4->name = "lefty of lefty";
/*add the values to BST*/
addBSTree(tree, myData1);
addBSTree(tree, myData2);
addBSTree(tree, myData3);
addBSTree(tree, myData4);
return tree;
}
void testAddNode() {
struct BSTree *tree = newBSTree();
struct data myData1;
struct data myData2;
struct data myData3;
struct data myData4;
myData1.number = 50;
myData1.name = "rooty";
addBSTree(tree, &myData1);
if (compare(tree->root->val, (TYPE *) &myData1) != 0) {
printf("addNode() test: FAIL to insert 50 as root ");
return;
}
else if (tree->cnt != 1) {
printf("addNode() test: FAIL to increase count when inserting 50 as root ");
return;
}
else printf("addNode() test: PASS when adding 50 as root ");
myData2.number = 13;
myData2.name = "lefty";
addBSTree(tree, &myData2);
if (compare(tree->root->left->val, (TYPE *) &myData2) != 0) {
printf("addNode() test: FAIL to insert 13 as left child of root ");
return;
}
else if (tree->cnt != 2) {
printf("addNode() test: FAIL to increase count when inserting 13 as left of root ");
return;
}
else printf("addNode() test: PASS when adding 13 as left of root ");
myData3.number = 110;
myData3.name = "righty";
addBSTree(tree, &myData3);
if (compare(tree->root->right->val, (TYPE *) &myData3) != 0) {
printf("addNode() test: FAIL to insert 110 as right child of root ");
return;
}
else if (tree->cnt != 3) {
printf("addNode() test: FAIL to increase count when inserting 110 as right of root ");
return;
}
else printf("addNode() test: PASS when adding 110 as right of root ");
myData4.number = 10;
myData4.name = "righty of lefty";
addBSTree(tree, &myData4);
if (compare(tree->root->left->left->val, (TYPE *) &myData4) != 0) {
printf("addNode() test: FAIL to insert 10 as left child of left of root ");
return;
}
else if (tree->cnt != 4) {
printf("addNode() test: FAIL to increase count when inserting 10 as left of left of root ");
return;
}
else printf("addNode() test: PASS when adding 10 as left of left of root ");
}
void testContainsBSTree() {
struct BSTree *tree = buildBSTTree();
struct data myData1;
struct data myData2;
struct data myData3;
struct data myData4;
struct data myData5;
myData1.number = 50;
myData1.name = "rooty";
myData2.number = 13;
myData2.name = "lefty";
myData3.number = 110;
myData3.name = "righty";
myData4.number = 10;
myData4.name = "lefty of lefty";
myData5.number = 111;
myData5.name = "not in tree";
if (containsBSTree(tree, &myData1))
printf("containsBSTree(): PASS when test containing 50 as root ");
else
printf("containsBSTree(): FAIL when test containing 50 as root ");
if (containsBSTree(tree, &myData2))
printf("containsBSTree(): PASS when test containing 13 as left of root ");
else
printf("containsBSTree(): FAIL when test containing 13 as left of root ");
if (containsBSTree(tree, &myData3))
printf("containsBSTree(): PASS when test containing 110 as right of root ");
else
printf("containsBSTree(): FAIL when test containing 110 as right of root ");
if (containsBSTree(tree, &myData4))
printf("containsBSTree(): PASS when test containing 10 as left of left of root ");
else
printf("containsBSTree(): FAIL when test containing 10 as left of left of root ");
if (!containsBSTree(tree, &myData5))
printf("containsBSTree(): PASS when test containing 111, which is not in the tree ");
else
printf("containsBSTree(): FAIL when test containing 111, which shouldn't be in the tree. ");
}
void testLeftMost() {
struct BSTree *tree = buildBSTTree();
struct data myData1;
struct data myData2;
struct data myData3;
struct data myData4;
myData1.number = 50;
myData1.name = "rooty";
myData2.number = 13;
myData2.name = "lefty";
myData3.number = 110;
myData3.name = "righty";
myData4.number = 10;
myData4.name = "lefty of lefty";
if (compare(_leftMost(tree->root), &myData4) == 0)
printf("_leftMost(): PASS left most of root ");
else
printf("_leftMost(): FAIL left most of root ");
if (compare(_leftMost(tree->root->left), &myData4) == 0)
printf("_leftMost(): PASS left most of left of root ");
else
printf("_leftMost(): FAIL left most of left of root ");
if (compare(_leftMost(tree->root->left->left), &myData4) == 0)
printf("_leftMost(): PASS left most of left of left of root ");
else
printf("_leftMost(): FAIL left most of left of left of root ");
if (compare(_leftMost(tree->root->right), &myData3) == 0)
printf("_leftMost(): PASS left most of right of root ");
else
printf("_leftMost(): FAIL left most of right of root ");
}
void testRemoveLeftMost() {
struct BSTree *tree = buildBSTTree();
struct Node *cur;
cur = _removeLeftMost(tree->root);
if (cur == tree->root)
printf("_removeLeftMost: PASS removing leftmost of root 1st try ");
else
printf("_removeLeftMost: FAIL removing leftmost of root 1st try ");
cur = _removeLeftMost(tree->root->right);
if (cur == NULL)
printf("_removeLeftMost: PASS removing leftmost of right of root 1st try ");
else
printf("_removeLeftMost: FAIL removing leftmost of right of root 1st try ");
cur = _removeLeftMost(tree->root);
if (cur == tree->root)
printf("_removeLeftMost: PASS removing leftmost of root 2st try ");
else
printf("_removeLeftMost: FAIL removing leftmost of root 2st try ");
}
void testRemoveNode() {
struct BSTree *tree = buildBSTTree();
struct Node *cur;
struct data myData1;
struct data myData2;
struct data myData3;
struct data myData4;
myData1.number = 50;
myData1.name = "rooty";
myData2.number = 13;
myData2.name = "lefty";
myData3.number = 110;
myData3.name = "righty";
myData4.number = 10;
myData4.name = "lefty of lefty";
_removeNode(tree->root, &myData4);
if (compare(tree->root->val, &myData1) == 0 && tree->root->left->left == NULL)
printf("_removeNode(): PASS remove left of left of root 1st try ");
else
printf("_removeNode(): FAIL remove left of left of root 1st try ");
_removeNode(tree->root, &myData3);
if (compare(tree->root->val, &myData1) == 0 && tree->root->right == NULL)
printf("_removeNode(): PASS remove right of root 2st try ");
else
printf("_removeNode(): FAIL remove right of root 2st try ");
_removeNode(tree->root, &myData2);
if (compare(tree->root->val, &myData1) == 0 && tree->root->left == 0)
printf("_removeNode(): PASS remove left of root 3st try ");
else
printf("_removeNode(): FAIL remove left of root 3st try ");
cur = _removeNode(tree->root, &myData1);
if (cur == NULL)
printf("_removeNode(): PASS remove root 4st try ");
else
printf("_removeNode(): FAIL remove root 4st try ");
}
int main(int argc, char *argv[])
{
testAddNode();
testContainsBSTree();
testLeftMost();
testRemoveLeftMost();
testRemoveNode();
return 0;
}
structs.h
/* You can modify the structure to store whatever you'd like in your BST */
struct data {
int number;
char *name;
};
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help