Problem: Almost a Forest
In this assignment, you will build many BST trees where each tree has a name. To store the names of all the trees, you will maintain a binary search tree for the tree names.
After building the trees, you will have to perform a set of operations and queries.
Here is an example. In this example fish, animals, birds, and fruit are part of the name BST. Each node of the name tree points to a BST of items. Here, the fish node points to a BST that contains the name and count of fishes. Note that all the green-colored nodes are of the same type of node structure and all the black-colored nodes are of the same type of node structure.
Input:
4 28 21
fish
animal
bird
fruit
animal cat 30
fish goldfish 50
animal dog 20
bird blackbird 10
animal bear 10
fruit mango 100
animal alligator 50
animal tiger 3
animal lion 3
fish swordfish 10
animal deer 5
animal cow 15
fish garfish 5
fish catfish 55
fish salmon 40
bird crow 20
bird dove 10
bird flamingo 15
fruit apple 50
fruit banana 50
fruit nectarine 10
fruit coconut 10
fruit peach 40
fruit apricot 30
fruit avocado 25
fruit cherry 100
fruit cranberry 100animal horse 6
search fruit avocado
search fish tilapia
search animal cow
search bird crow
search bird cow
search animal cat
item_before animal deer
height_balance animal
height_balance bird
height_balance fish
search flower rose
count animal
count fruit
delete animal cat
search animal cat
count animal
delete fish swordfish
delete fruit avocado
delete_name animal
reduce fruit mango 50
search fruit mango
Output:
animal bird fish fruit
===animal===
alligator bear cat cow deer dog horse lion tiger
===bird===
blackbird crow dove flamingo
===fish===
catfish garfish goldfish salmon swordfish
===fruit===
apple apricot avocado banana cherry coconut cranberry mango nectarine peach
25 avocado found in fruit
tilapia not found in fish
15 cows found in animal
20 crow found in bird
cow not found in bird
30 cats found in animal
the item before deer: 4
animal: left height 1, right height 3, difference 2, not balanced
bird: left height -1, right height 2, difference 3, not balanced
fish: left height 1, right height 1, difference 0, balanced
the flower does not exist
animal count 142
fruit count 515
cat deleted from animal
cat not found in animal
animal count 112
swordfish deleted from fish
avocado deleted from fruit
animal deleted
mango reduced
50 mango found in fruit
Solution:
/*
* assignment4.c
*
* Created on: Jul 22, 2021
* Author: thanh
*/
#include
#include
#include
#include
#define MAXLEN 30
typedef struct itemNode
{
char name[MAXLEN];
int count;
struct itemNode *left, *right;
} itemNode;
typedef struct treeNameNode
{
char treeName[MAXLEN];
struct treeNameNode *left, *right;
itemNode *theTree;
} treeNameNode;
FILE *outputFile;
/**
* Try to create the tree node
*/
treeNameNode* createTreeNameNode(char *name)
{
treeNameNode *tree = (treeNameNode*) malloc(sizeof(treeNameNode));
tree->left = tree->right = NULL;
tree->theTree = NULL;
strcpy(tree->treeName, name);
return tree;
}
/**
* Insert node to tree
*/
treeNameNode* insertNameNode(treeNameNode *root, treeNameNode *node)
{
if (root == NULL)
{
/*If this is empty tree. Just return the node*/
return node;
}
else
{
if (0 >= strcmp(node->treeName, root->treeName))
{
/* Try to insert to left node */
if (root->left != NULL)
{
root->left = insertNameNode(root->left, node);
}
else
{
root->left = node;
}
}
else
{
/* Try to insert to right node */
if (root->right != NULL)
{
root->right = insertNameNode(root->right, node);
}
else
{
root->right = node;
}
}
return root;
}
}
/**
* Based on the data in the file, it will insert them to the name
* tree and then finally return the root of the name tree
*/
treeNameNode* buildNameTree(treeNameNode *root, FILE *input, int nodeCnt)
{
treeNameNode *tmp;
for (int i = 0; i < nodeCnt; i++)
{
char name[MAXLEN];
/* Read tree node name */
fscanf(input, "%s", name);
/* Create the name node */
tmp = createTreeNameNode(name);
/* Insert to tree */
root = insertNameNode(root, tmp);
}
return root;
}
/* Create the item node*/
itemNode* createItemTreeNode(char *treeName, char *itemName, int count)
{
itemNode *item = (itemNode*) malloc(sizeof(itemNode));
item->count = count;
item->left = item->right = NULL;
strcpy(item->name, itemName);
return item;
}
/*
* Print the tree with order by name
*/
void printTreeInOderByName(treeNameNode *root)
{
if (root != NULL)
{
printTreeInOderByName(root->left);
fprintf(outputFile, "%s ", root->treeName);
printTreeInOderByName(root->right);
}
}
/**
* Print the tree with oder by item
*/
void printTreeInOderByItem(itemNode *root)
{
if (root != NULL)
{
printTreeInOderByItem(root->left);
fprintf(outputFile, "%s ", root->name);
printTreeInOderByItem(root->right);
}
}
/**
* Print tree with order by item with format
*/
void printOderByItemFormat(treeNameNode *root)
{
if (root != NULL)
{
printOderByItemFormat(root->left);
fprintf(outputFile, "===%s===\n", root->treeName);
printTreeInOderByItem(root->theTree);
fprintf(outputFile, "\n");
printOderByItemFormat(root->right);
}
}
/**
* this function takes the root of the
* name tree and prints the data of the name tree and the corresponding item trees in the format
* shown in the sample output
*/
void traverse_in_traverse(treeNameNode *root)
{
printTreeInOderByName(root);
fprintf(outputFile, "\n");
printOderByItemFormat(root);
}
/**
* This function takes a name string and search this name in the name tree and returns that node.
*/
treeNameNode* searchNameNode(treeNameNode *root, char name[MAXLEN])
{
if (root == NULL)
{
return 0;
}
else
{
if (strcmp(root->treeName, name) == 0)
{
return root;
}
else if (strcmp(root->treeName, name) > 0)
{
return searchNameNode(root->left, name);
}
else
{
return searchNameNode(root->right, name);
}
}
}
/**
* Insert item to node
*/
itemNode* insertItem(itemNode *root, itemNode *item)
{
if (root == NULL)
{
return item;
}
else
{
if (strcmp(item->name, root->name) > 0)
{
if (root->right != NULL)
{
root->right = insertItem(root->right, item);
}
else
{
root->right = item;
}
}
else
{
if (root->left != NULL)
{
root->left = insertItem(root->left, item);
}
else
{
root->left = item;
}
}
return root;
}
}
/**
* Build tree with the item from input file
*/
treeNameNode* buildTreeByItemFromInputFile(treeNameNode *root, FILE *input, int size)
{
itemNode *item;
for (int j = 0; j < size; j++)
{
char name[MAXLEN];
char nameItem[MAXLEN];
int count;
fscanf(input, "%s %s %d\n", name, nameItem, &count);
item = createItemTreeNode(name, nameItem, count);
treeNameNode *temp = searchNameNode(root, name);
temp->theTree = insertItem(temp->theTree, item);
}
return root;
}
/**
* Delete the item
*/
void deleteItem(itemNode *root)
{
if (root != NULL)
{
deleteItem(root->left);
deleteItem(root->right);
free(root);
}
}
/**
* Delete tree
*/
void deleteTree(treeNameNode *root)
{
if (root != NULL)
{
if (root->theTree != NULL)
deleteItem(root->theTree);
deleteTree(root->left);
deleteTree(root->right);
free(root);
}
}
/**
* Search item from the node
*/
itemNode* searchItemNode(itemNode *root, char name[MAXLEN])
{
if (root == NULL)
{
return 0;
}
else
{
if (strcmp(root->name, name) == 0)
{
return root;
}
else if (strcmp(root->name, name) > 0)
{
return searchItemNode(root->left, name);
}
else
{
return searchItemNode(root->right, name);
}
}
}
/**
* Find the command from the input file
*/
void findTheCommandFromInputFile(treeNameNode *root, FILE *input)
{
char name[MAXLEN];
char nameItem[MAXLEN];
fscanf(input, "%s %s", name, nameItem);
treeNameNode *node = searchNameNode(root, name);
if (node == 0)
fprintf(outputFile, "%s does not exist\n", name);
else
{
itemNode *tempItemNode;
tempItemNode = searchItemNode(node->theTree, nameItem);
if (tempItemNode == 0)
fprintf(outputFile, "%s not found in %s\n", nameItem, node->treeName);
else
fprintf(outputFile, "%d %s found in %s\n", tempItemNode->count, tempItemNode->name, node->treeName);
}
}
/**
* Count the item before node name
*/
int countItemBefore(itemNode *root, char names[MAXLEN])
{
int cnt = 0;
if (root == NULL)
{
return 0;
}
else if (strcmp(root->name, names) < 0)
{
cnt++;
cnt += countItemBefore(root->left, names);
cnt += countItemBefore(root->right, names);
}
else
{
cnt += countItemBefore(root->left, names);
}
return cnt;
}
/**
* Handle before command
*/
void handleBeforeCommand(treeNameNode *root, FILE *input)
{
char name[MAXLEN];
char nameItem[MAXLEN];
fscanf(input, "%s %s", name, nameItem);
treeNameNode *tmp = searchNameNode(root, name);
itemNode *node = searchItemNode(tmp->theTree, nameItem);
int count = 0;
count = countItemBefore(tmp->theTree, nameItem);
fprintf(outputFile, "item before %s: %d\n", node->name, count);
}
/*8
* Get height of tree
*/
int getHeightTree(itemNode *root)
{
int leftH = 0;
int rightH = 0;
if (root == NULL)
{
return -1;
}
leftH = getHeightTree(root->left);
rightH = getHeightTree(root->right);
if (leftH > rightH)
{
return 1 + leftH;
}
else
{
return 1 + rightH;
}
}
/**
* Print the balance command
*/
void handleBalanceCommand(treeNameNode *root, FILE *input)
{
char names[MAXLEN];
fscanf(input, "%s", names);
treeNameNode *nodes = searchNameNode(root, names);
int left_height = getHeightTree(nodes->theTree->left);
int right_height = getHeightTree(nodes->theTree->right);
int diff = abs(left_height - right_height);
if (diff >= 2)
{
fprintf(outputFile, "%s: left height %d, right height %d, difference %d, not balanced\n", nodes->treeName, left_height,
right_height, diff);
}
else
{
fprintf(outputFile, "%s: left height %d, right height %d, difference %d, balanced\n", nodes->treeName, left_height, right_height,
diff);
}
}
/**
* Get total count
*/
int getTotalCount(itemNode *root)
{
int sum = 0;
if (root != NULL)
{
sum += getTotalCount(root->left);
sum += getTotalCount(root->right);
return sum + root->count;
}
return 0;
}
/**
* Handle count command
*/
void handleCountCommand(treeNameNode *root, FILE *input)
{
char names[MAXLEN];
fscanf(input, "%s", names);
treeNameNode *node = searchNameNode(root, names);
int sum = getTotalCount(node->theTree);
fprintf(outputFile, "%s count %d\n", node->treeName, sum);
}
/**
* Get min node by name
*/
treeNameNode* getMinNodeByName(treeNameNode *root)
{
treeNameNode *node = root;
while (node && node->left != NULL)
{
node = node->left;
}
return node;
}
/**
* Get min node by item
*/
itemNode* getMinNodeByItem(itemNode *root)
{
itemNode *node = root;
while (node && node->left != NULL)
{
node = node->left;
}
return node;
}
/**
* Delete item node
*/
itemNode* deleteItemNode(itemNode *root, char names[MAXLEN])
{
if (root == NULL)
{
return root;
}
if (strcmp(names, root->name) < 0)
{
root->left = deleteItemNode(root->left, names);
}
else if (strcmp(names, root->name) > 0)
{
root->right = deleteItemNode(root->right, names);
}
else
{
if (root->left == NULL)
{
itemNode *tmp = root->right;
free(root);
return tmp;
}
else if (root->right == NULL)
{
itemNode *tmp = root->left;
free(root);
return tmp;
}
itemNode *tmp = getMinNodeByItem(root->right);
strcpy(root->name, tmp->name);
root->count = tmp->count;
root->right = deleteItemNode(root->right, tmp->name);
}
return root;
}
/**
* Handle delete command
*/
void handleDeleteCommand(treeNameNode *root, FILE *input)
{
char name[MAXLEN];
char nameItem[MAXLEN];
fscanf(input, "%s %s", name, nameItem);
treeNameNode *node = searchNameNode(root, name);
itemNode *outputItem = searchItemNode(node->theTree, nameItem);
char deleteNames[MAXLEN];
strcpy(deleteNames, outputItem->name);
node->theTree = deleteItemNode(node->theTree, nameItem);
fprintf(outputFile, "%s deleted from %s\n", deleteNames, node->treeName);
}
/**
* Delete name node
*/
treeNameNode* deleteNameNode(treeNameNode *root, char names[MAXLEN])
{
if (root == NULL)
{
return root;
}
if (strcmp(names, root->treeName) < 0)
{
root->left = deleteNameNode(root->left, names);
}
else if (strcmp(names, root->treeName) > 0)
{
root->right = deleteNameNode(root->right, names);
}
else
{
if (root->left == NULL)
{
treeNameNode *tmp = root->right;
free(root);
return tmp;
}
else if (root->right == NULL)
{
treeNameNode *tmp = root->left;
free(root);
return tmp;
}
treeNameNode *tmp = getMinNodeByName(root->right);
strcpy(root->treeName, tmp->treeName);
root->right = deleteNameNode(root->right, tmp->treeName);
}
return root;
}
/**
* Handle delete name command
*/
void handleDeleteNameCommand(treeNameNode *root, FILE *input)
{
char names[MAXLEN];
fscanf(input, "%s", names);
treeNameNode *node = searchNameNode(root, names);
char treeNameFromTree[MAXLEN];
strcpy(treeNameFromTree, node->treeName);
deleteItem(node->theTree);
root = deleteNameNode(root, names);
fprintf(outputFile, "%s deleted\n", treeNameFromTree);
}
/**
* Handle reduce command
*
*/
void handleReduceCommand(treeNameNode *root, FILE *input)
{
char names[MAXLEN];
char nameItem[MAXLEN];
int reduce;
fscanf(input, "%s %s %d", names, nameItem, &reduce);
treeNameNode *node = searchNameNode(root, names);
itemNode *items = searchItemNode(node->theTree, nameItem);
items->count -= reduce;
if (items->count <= 0)
{
fprintf(outputFile, "%s reduced\n", items->name);
node->theTree = deleteItemNode(node->theTree, nameItem);
}
fprintf(outputFile, "%s reduced\n", items->name);
}
/**
* Handle command
*/
treeNameNode* handleCommand(treeNameNode *root, FILE *input, int Q)
{
for (int k = 0; k < Q; k++)
{
char querie[MAXLEN];
fscanf(input, "%s", querie);
if (strcmp(querie, "search") == 0)
findTheCommandFromInputFile(root, input);
else if (strcmp(querie, "item_before") == 0)
handleBeforeCommand(root, input);
else if (strcmp(querie, "height_balance") == 0)
handleBalanceCommand(root, input);
else if (strcmp(querie, "count") == 0)
handleCountCommand(root, input);
else if (strcmp(querie, "delete") == 0)
handleDeleteCommand(root, input);
else if (strcmp(querie, "delete_name") == 0)
handleDeleteNameCommand(root, input);
else if (strcmp(querie, "reduce") == 0)
handleReduceCommand(root, input);
}
return root;
}
/**
* Main function
* j o h n n y t u o t - g m a i l - c o m
*/
int main(int argc, char **argv)
{
FILE *input = fopen("in.txt", "r");
outputFile = fopen("out.txt", "w");
if (input == NULL || outputFile == NULL)
{
printf("ERROR when open the input and output file.\nPlease check the input: in.txt.\n");
return 1;
}
treeNameNode *root = NULL;
int N, I, Q;
fscanf(input, "%d %d %d", &N, &I, &Q);
root = buildNameTree(root, input, N);
root = buildTreeByItemFromInputFile(root, input, I);
traverse_in_traverse(root);
root = handleCommand(root, input, Q);
deleteTree(root);
fclose(input);
fclose(outputFile);
return 0;
}