Homework file uploaded in pdf
COP 3502C Programming Assignment # 4 Binary Search Tree Read all the pages before starting to write your code Introduction: For this assignment you have to write a c program that will use Binary Search Tree (BST) What should you submit? Write all the code in a single file and upload the .c file to Webcourses. Please include the following commented lines in the beginning of your code to declare your authorship of the code: /* COP 3502C Assignment 4 This program is written by: Your Full Name */ Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students for explaining any part of the code in order to better assess your authorship and for further clarification if needed. Caution!!! Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is a violation of the policy. I may report to office of student conduct and an investigation can easily trace the student who shared/posted it. Also, getting a part of code from anywhere will be considered as cheating. Deadline: See the deadline in Webcourses. The assignment will accept late submission up to 24 hours after the due date time with 10% penalty. After that the assignment submission will be locked. An assignment submitted by email will not be graded and such emails will not be replied according to the course policy. What to do if you need clarification on the problem? Write an email to the TA and put the course teacher in the cc for clarification on the requirements. I will also create a discussion thread in webcourses, and I highly encourage you to ask your question in the discussion board. Maybe many students might have same question as you. Also, other students can reply, and you might get your answer faster. How to get help if you are stuck? According to the course policy, all the helps should be taken during office hours. There Occasionally, we might reply in email. 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, animal, bird, 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 name and count of fishes. Note that all the green colored nodes are of same type of node structure and all the black colored nodes are of same type of node structure. Input Specification: You have to read the inputs from in.txt file. There will many strings in this file and you can assume that all the strings will be lower case letter and the maximum length of a string is 30 character. For simplicity, use static array of char to store a string. The first line of the file contains three integers N, I, and Q, where N represents number of Tree Names, I represents the total number of items in the list to be inserted to all the trees, and Q represents the number of queries listed in the input file. After the first line, next N lines will contain the list of Names of the trees and you need to insert them to a Name tree. Next, I lines will contain the list of items to be inserted in different trees. Each line of the list contains two strings and one integer. The first string contains the name of that tree, second string contains the item name, and then the last integer contains the count of that item. You have to insert the item in the tree with that tree name. You need to use the item name as the key of the BST. Also note that the item count need to be added to the node as well. [Assumption: You can assume that a tree name as well as an item name will not be repeated in the input] After the I lines, the next Q lines will contain a set of queries and you need to process them. Here is the list of queries: • search: search for a particular item in a given tree and display the count of the item if it is found. Otherwise, prints item not found. However, if the tree does not exist, then it prints tree does not exist o [Example: search fruit avocado should search for avocado in the fruit tree and then prints the count of avocado. If the fruit tree exists, but the avocado does not exist, it should print “not found”. However, if fruit tree does not exist, then it should print tree does not exist. • item_before: this command counts the items in a given tree coming before a given item name (alphabetically). o [For example, if your query is like this item_before animal deer, it should print 4 as cat, bear, alligator, and cow come before deer alphabetically.] • height_balance: It finds whether a given tree is height balanced or not. In order to do that, you need to know the height of left sub tree and then height of right sub tree. If their height difference’s absolute value is more than 1, then we say the tree is imbalanced. In this assignment, a tree with 1 node, will be consider as height 0, and a tree with no node will be considered as height -1. o [Example: height_balance animal, will print, left height 1, right height 3, difference 2, not balanced] • count: this command prints the total number of items in a given tree. o [Example: count animal, should print 142 (as 30 + 20+ 10 +50 +3 + 3 +5 +15 = 142)] • reduce: this command reduces the count of an item in a given tree. The min value of the count needs to be >0. So, if it becomes <=0, you need to delte the node] //this command is optional. if you implement it, you will get 5 points extra credit. so, keep it aside to do later if you get time. o [example: reduce fruit mango 50 will reduce the total mango to 50 from 100.] o [another example: reduce goldfish 50 will delete the node as goldfish is reduced to 0] • delete: this command deletes an item from a given tree. o [example: delete fruit avocado will delete the avocado node from the fruit tree] • delete_name: this command delte the entire tree of a given name. o [example: delete_name animal will delete the animal tree as well as animal node from the name tree] sample 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 100 animal 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 specification: you have to write all the output to an out.txt file. you are allowed to use a global variable for outfile pointer to simplify your function parameters. after building the tree, you should print the trees in inorder in the specified format shown in the sample output bellow. sample 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 cow found in animal 20 crow found in bird cow not found in bird 30 cat found in animal 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 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 implementation restriction.: 1. you have to use the following structure. you are allowed to modify the structure if needed. 2. 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; 2.in addition to typical functions of tree implementation, you must have to implement the following functions: i. createtreenamenode() ii. treenamenode* buildnametree(…..): based on the data in the file, it will insert them you="" need="" to="" delte="" the="" node]="" this="" command="" is="" optional.="" if="" you="" implement="" it,="" you="" will="" get="" 5="" points="" extra="" credit.="" so,="" keep="" it="" aside="" to="" do="" later="" if="" you="" get="" time.="" o="" [example:="" reduce="" fruit="" mango="" 50="" will="" reduce="" the="" total="" mango="" to="" 50="" from="" 100.]="" o="" [another="" example:="" reduce="" goldfish="" 50="" will="" delete="" the="" node="" as="" goldfish="" is="" reduced="" to="" 0]="" •="" delete:="" this="" command="" deletes="" an="" item="" from="" a="" given="" tree.="" o="" [example:="" delete="" fruit="" avocado="" will="" delete="" the="" avocado="" node="" from="" the="" fruit="" tree]="" •="" delete_name:="" this="" command="" delte="" the="" entire="" tree="" of="" a="" given="" name.="" o="" [example:="" delete_name="" animal="" will="" delete="" the="" animal="" tree="" as="" well="" as="" animal="" node="" from="" the="" name="" tree]="" sample="" 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="" 100="" animal="" 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="" specification:="" you="" have="" to="" write="" all="" the="" output="" to="" an="" out.txt="" file.="" you="" are="" allowed="" to="" use="" a="" global="" variable="" for="" outfile="" pointer="" to="" simplify="" your="" function="" parameters.="" after="" building="" the="" tree,="" you="" should="" print="" the="" trees="" in="" inorder="" in="" the="" specified="" format="" shown="" in="" the="" sample="" output="" bellow.="" sample="" 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="" cow="" found="" in="" animal="" 20="" crow="" found="" in="" bird="" cow="" not="" found="" in="" bird="" 30="" cat="" found="" in="" animal="" 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="" 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="" implementation="" restriction.:="" 1.="" you="" have="" to="" use="" the="" following="" structure.="" you="" are="" allowed="" to="" modify="" the="" structure="" if="" needed.="" 2.="" 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;="" 2.in="" addition="" to="" typical="" functions="" of="" tree="" implementation,="" you="" must="" have="" to="" implement="" the="" following="" functions:="" i.="" createtreenamenode()="" ii.="" treenamenode*="" buildnametree(…..):="" based="" on="" the="" data="" in="" the="" file,="" it="" will="" insert="">