// trees.cpp : Defines the entry point for the console application.
//

Ex.
// tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "string.h"
struct node
	{
		char data;
		node *right;
		node *left;
		
	};

class tree                      //create a tree class
{
public:
    void Initialize(void);
	void HeadInsert (int number);
	int Search (node *lastpointer,node *currentpointer, char letter, char direction,int length);
	void Insert (node *lastpointer,node *currentpointer, char letter, char direction);
	void Print(node *here);
	void Visit(node *here);
	node *head;
	node *end;
};


int main(int argc, char* argv[])
{
	int size=0;
	int num;
	int length, length1,length2,x,k;
	char response,direction,dummy;
	char sentence[80];
    tree list1, list2;
	list1.Initialize();
	list2.Initialize();
	
		cout<<"type in a sentence"<<endl;
		cin.getline(sentence,80);
		
		strupr(sentence);
		x = strlen(sentence);
		for (k=0;k<x;k++)
		{
		size++;
			if (size==1)
	            	list1.HeadInsert(sentence[k]);
			else if (size==2)
	            	list2.HeadInsert(sentence[k]);
			else if (sentence[k]!=' ') 
			{//
				length1 =list1.Search(list1.head,list1.head,sentence[k],'N',0);
				length2 =list2.Search(list2.head,list2.head,sentence[k],'N',0);
				//cout<<num<<" "<<length1<<" "<<length2<<" "<<endl;
				if (length1 <= length2 )
				 list1.Insert(list1.head,list1.head,sentence[k],'N');
				
                else
				list2.Insert(list2.head,list2.head,sentence[k],'N');

			}

		}

	
	cout<<"List 1"<<endl;
	list1.Print(list1.head);
	cout<<"List 2"<<endl;
    list2.Print(list2.head);

		return 0;
}

// functions
void tree:: HeadInsert (int number)
{
    node *temp;
    temp = new node;
    temp->data = number;    // put the data in the node
    temp ->right = NULL;
	temp->left=NULL;
    head = temp;             // move the start of the list to the start of the new node
    end=head;                //place the end at the last node
}


void tree:: Initialize (void)
{
    head=NULL;
    end=NULL;
	
}
 
void tree::  Print (node *here)
{
      
	   	
	   
		
		  
		   Visit(here);

	if (here->left !=NULL)  //traverse left
		   Print(here->left);
	
	if (here->right !=NULL)
		   Print(here->right); //traverse right
	   
    
}
void tree::  Visit (node *here)
{    
	   	   cout<<here->data<<endl;	   
    
}
int tree::  Search (node *lastpointer,node *currentpointer, char letter, char direction,int length)
{
   
   

   if (currentpointer != NULL)           //while there is a node
   {                                 
	  if (letter <= currentpointer->data)
	  {
		  length++;
		  Search(currentpointer,currentpointer->left, letter,'L',length);
	  }
	else if (letter > currentpointer->data)
	  {
		  length++;
		  Search(currentpointer,currentpointer->right, letter,'R',length);
	  }

	  
	}
   else if(currentpointer==NULL )
   {
	   
	return(length);
   }
}

void tree::  Insert (node *lastpointer,node *currentpointer, char letter, char direction)
{
   
   

   if (currentpointer != NULL)           //while there is a node
   {                                 
	  if (letter <= currentpointer->data)
	  {
		 
		  Insert(currentpointer,currentpointer->left, letter,'L');
	  }
	else if (letter > currentpointer->data)
	  {
		  
		  Insert(currentpointer,currentpointer->right, letter,'R');
	  }

	  
	}
   else if(currentpointer==NULL )
   {
	  
	node *temp;
    temp = new node;
    temp->data = letter;    // put the data in the node
    temp ->right = NULL;
	temp->left=NULL;
    if (direction=='L')
		lastpointer->left=temp;
	if (direction=='R')
		lastpointer->right=temp;

   }
}

