You are to write a program that creates and maintains a binary search tree of items in a super market. Each item has a name and a value. All item names will be lowercase alphabetic strings of less than 30 letters. All values will be positive real numbers representing prices. Also, for each node in the tree, you are to maintain the value of all of the items in that subtree. Your tree should be “sorted” based on alphabetical ordering of the item names as determined by strcmp. Your program must allow the user to do the following:
1) Add an item to the inventory
2) Delete an item from the inventory
3) Print out all of the items in the inventory in alphabetical order.
4) Print out the value of all items underneath the subtree of a given item.
For example, if the user adds these items:
a) “soap”, $2.95
b) “raisins”, $2.00
c) “jellybeans”, $5.00
d) “tea”, $1.95
Input File Specification (inventory.txt)
The first line of the input file will contain a single positive integer, n, representing the number of commands to execute. The following n lines will contain one command each, in the other they are to be executed.
The first number of each of these lines will be either 1, 2, 3 or 4, to signify the choices listed above.
If the choice is 1, it will be followed by the name of the item added and its price (as a number), both separated by spaces.
If the choice is 2, it will be followed by the name of the item to be deleted.
Choice 3 will be on a line by itself.
Choice 4 will be followed by a single string storing an item.
Output Specification
For each command, your program should provide some output.
The output provided by each command should be separated by a blank line.
For choice 1, if the item to be added is NOT in the tree, output a line with the following format:
item has been added to the stock.
where item is the name of the item added. If the item is ALREADY in the tree, output a line with the following format:
Sorry, item is already in stock. No changes made.
For choice 2, if the item to be deleted is IN the tree and is successfully deleted, output a line with the following format:
item has been deleted from the stock.
If the item is NOT in the tree, then output a line with the following format:
Sorry, item couldn’t be deleted because it’s not in stock.
For choice 3, the first line should read:
Here is a list of the items in stock:
Each following line should have information about one item and the list should be in alphabetical order by item name. Here is the format for one of these lines:
item $price
The price should be printed out to two decimal places exactly.
Finally, for choice 4, print out the sum of the values of all the items in the subtree rooted by the designated item. If this item is NOT in the tree, $0.00 should be printed out. Here is the format for the output for this option.
The value of all the items underneath item is $price.
Implementation Restrictions
You must store the data in nodes of a binary tree. Each binary tree node must store 3 pieces of information: the name of the item, its price, and the sum of the prices of all the items in its subtree.
Sample Input File
11
2 soap
1 soap 2.95
1 raisins 2.00
1 jellybeans 5.00
1 tea 1.95
4 raisins
3
2 raisins
4 soap
4 cereal
1 soap 3.50
Sample Output
Sorry, soap couldn’t be deleted because it’s not in stock.
soap has been added to the stock.
raisins has been added to the stock.
jellybeans has been added to the stock.
tea has been added to the stock.
The value of all the items underneath raisins is $7.00.
Here is a list of the items in stock:
jellybeans $5.00
raisins $2.00
soap $2.95
tea $1.95
raisins has been deleted from the stock.
The value of all the items underneath soap is $9.90.
The value of all the items underneath cereal is $0.00.
Sorry, soap is already in stock. No changes made.
