Question

Project 4: 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

George Eamon Cappuccio McCluskey Carolina

Answer 1

#include <bits/stdc++.h>
using namespace std;
class node
{
   public:
   int data;
   node* left;
   node* right;
};
int Height(node* node)
{
   if (node == NULL)
       return 0;
   else
   {
       int lHeight = Height(node->left);
       int rHeight = Height(node->right);
  
       if (lHeight > rHeight)
           return(lHeight + 1);
       else return(rHeight + 1);
   }
}
node* newNode(int data)
{
   node* Node = new node();
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;
  
   return(Node);
}
  
int main()
{
   node *root = newNode(1);

   root->left = newNode(2);
   root->right = newNode(3);
   root->left->left = newNode(4);
   root->left->right = newNode(5);
  
   cout << "Length of tree is " << V(root);
   return 0;
}