Order Now  +1 678 648 4277 

Binary Search tree Assignment Solution


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; }