/* ===================================================================*\



  filename: bin_tree.C


  A PROGRAM THAT READS WORDS FROM STANDARD INPUT UNTILL END OF FILE.

  THE PROGRAM THEN PRINTS AN ALPHABETICAL LISTING OF THE WORDS TOGETHER

  WITH THEIR FREQUENCY AND THEN THE SAME LIST SORTED BY FREQUENCY.



  PROGRAMMER:  RiNN
  INSTRUCTOR:  Dr. Robert Sczech 
  Class:       CS102 S98
  Date:        Tuesday March 31, 1998 



\*=====================================================================*/

#include                   //iostream Header
#include                   //String   Header



struct tnode{
 String data;
 int count;
 tnode *left, *right;
};
typedef tnode* tree;

tree wtree, ctree;


//INSERT WORD INTO TREE, SORTING ALPHABETICALLY
void winsert(tree &t, String word);

//PRINT wtree, AND CALL cinsert 
void wtraverse(tree t);

//INSERT INTO ctree, SORTING BY FREQUENCY
void cinsert(tree &t, String word, int count);

//PRINT ctree
void ctraverse(tree t);


//MAIN FUNCTION
int main(){
   wtree=NULL; ctree=NULL;
   String word;
   cout << " Please enter input. Push ctrl d to stop input" << endl;

   cin >> word;
   while (!cin.eof()) {
	winsert(wtree, word);
	cin >> word;
   }

   cout << endl <<" Alphabetical order" << endl;
   wtraverse(wtree);
   cout << " Frequency order" << endl;
   ctraverse(ctree);
   return 0;
}



void winsert(tree &t, String word){
  if(t == NULL){ //Attach New NODE
    t = new tnode;
    t->left = NULL;
    t->right= NULL;
    t->data= word;
    t->count = 1;
 }

 else{ 
    if (word == t->data)
       t -> count++;
    else if(word < t->data)
       winsert(t->left, word);
    else
       winsert(t->right,word);
 }
}

void wtraverse(tree t){
 if (t!=NULL){
   wtraverse(t->left);
   cout << t->count << " " << t->data << endl;  
   cinsert(ctree, t->data, t->count);
   wtraverse(t->right);
 }
}

void cinsert(tree &t, String word, int count){
 if(t==NULL){
  t=new tnode;
  t->left=NULL;
  t->right=NULL;
  t->data=word;
  t->count=count;
 }
  else{
   if(t->count > count)
     cinsert(t->left, word, count);  //INSERT LEFT
   else
     cinsert(t->right, word, count); //INSERT RIGHT
  }
}

void ctraverse(tree t){
  if(t!=NULL){
   ctraverse(t->left);
   cout << t->count << " " << t->data << endl;
   ctraverse(t->right);
 }
}