CIS 22 Assignment 5 Binary
Search Trees
This
program will construct a binary search tree (actually, two of
them). You will read in a series of
data values, each of which contains a number.
You will create a binary search tree based on these numbers. Your program will traverse the tree,
printing each number and how many times that number occurs in the tree. Then the program will repeat the process
after reading the numbers in a different order.
Step 1: use the C++ BSTree data structure discussed in class to
process the binary tree. However you will need to transform it into a template
class and add a remove method.
In the
process of inserting an item, if the item is a duplicate number (it is equal to
the value stored at a node), you will not add a new node. Instead, increment a counter of how many
times that value was seen. For example,
if 5 is stored at a node, and another 5 comes along, then the count for 5 will
go to 2; the next 5 will change the count to 3, and so on.
Step 2: For the processing phase, traverse each tree in three ways: using
clearly marked inorder, preorder, and postorder traversals. For each traversal, simply print the entire
info field of the node, that is, the number and how many times it occurs).
Finally, print the number that occurs most often in
the data set.
Step 3: remove 3 items from the
tree using the remove method you added and repeat step 2 indicating which items
are removed,
but this time enter the data values so that the most frequent item is now the
root of the tree.
DATA: Use the data listed on the
second page of this assignment
(You can read the data manually or from a file).
BSTree type: create
a data type called Item that will hold the information (value and frequency
counter) that is supposed to be stored in each of the tree nodes. Then use the
template facility to create a binary search of type Item.
Modules: Each
data structure used should exist as a separate module in separate file.
Comments: Do not forget to comment
your program.
You
should hand in all source code files and the output of your program.
Data for assignment 5:
107
60
230
45
52
400
150
60
132
111
47
80
10
90
315
75
52
520
22
47
59
107
60
2
11
350
270
106
85
60
52