Tree Sort
Develop a C++ program that will recursively alphabetize a set of strings in a user-specified file using the tree sort algorithm explained in the lectures while maintaining a balanced binary tree at all times.
The instructor will test your program with an input file containing:
Max Hank Jet Frisky Chata Richard Nan Sam Thomas Karen Gerri Ingrid Alan Dana
When done print out the contents of the tree with inorder traversal in a tabular format similar to the following:
NODE
|
LEFT
|
RIGHT
|
HEIGHT
|
BALANCE
|
Clarise
|
null
|
null
|
1
|
0
|
Fred
|
Clarise
|
Henry
|
2
|
0
|
Henry
|
null
|
null
|
1
|
0
|
Jane
|
Fred
|
Nan
|
4
|
-1
|
Mark
|
null
|
null
|
1
|
0
|
Nan
|
Mark
|
Susan
|
3
|
-1
|
Ryan
|
null
|
null
|
1
|
0
|
Susan
|
Ryan
|
Tammy
|
2
|
0
|
Tammy
|
null
|
null
|
1
|
0
|
Extra Credit (1 point):
enhance
your program to allow for duplicates in the input data (but do NOT put duplicate entries in the tree). Expand the above table to contain a column for MULTIPLICITY, which keeps track of the number of duplicates encountered for each node in the tree. Turn in a SEPARATE program for this extra credit option, called project4_ec.cpp.
Extra Credit (2
more
points)
further
enhance
your program, in a separate program called project4_ec.cpp, as explained in the lectures so it will correctly alphabetize the following set of strings. If you do this extra credit option you do NOT need to do a separate program for the above 1-point extra credit option – this 2-point option should include the detection of multiplicities, for a possible 3 extra credit points.
Max Hank Jet Frisky Chata Juvy Winky Bridget Tiger Richard Thomas
Dixie Sewald Karinda Isabella Donato Hipolita SanJuan Kuko
Mariano Julio Rodriguez Salas Consuelo Irene Cruz Paredo
Marcos Paciencia Pitang Conrad Antonio Ding Josefa Nene