// tree1.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include<iostream>
#include"windows.h"
#include<string>
using namespace std;
const int max_item=50;
enum relationtype{LESS,GREATER,EQUAL};

class student        //class for item type
{
public:
	student();
	void intialize(int,string);
	relationtype compareto(student)const;
	void print();
private:
	int id;
	string name;
};
class node                        // for node type.
{
public:
	student info;
	node* next;
};
student::student()
{
	id=0;
	name=" ";
}
void student::intialize(int a,string b)
{
	id=a;
	name=b;
}
void student::print()
{
	cout<<"\n the student that has id number  ' "<<id<<" '  ";	
	cout<<" his name is   ( "<<name<<"  )"<<endl<<endl;
}

relationtype student::compareto(student st1)const    //for comparing
{
	if(id<st1.id)
	{
		return LESS;
	}
	else if(id>st1.id)
	{
		return GREATER;
	}
	else 
		return EQUAL;
}
student get_data()
{
	student st;
	int a;string b;
	cout<<" enter the student id :\n";
	cin>>a;
	cout<<" enter the student name :\n ";
	cin>>b;
	st.intialize(a,b);
	return st;
}
class node_tree                       // for node type.
{
public:
	student info;
	node_tree* left;
	node_tree* right;
};
class tree
{
private:
	node_tree *root;
public:
	tree();
	~tree();
	void insert(student);
	void delete1_item(student);
	void retrieve_ITEM(student,bool&);
	int lengthis()const;
	bool is_impty()const;
	bool is_full()const;
	void print();
	void copy_tree(tree&);
};
tree::tree()
{
	root=NULL;
}
bool tree::is_impty() const
{
	if(root==NULL)
	{
		return true;
	}
	else return false;
}
void make_impty_tree(node_tree *node)
{
	if(node!=NULL)
	{
		make_impty_tree(node->left);
		make_impty_tree(node->right);
		delete node;
	}
}
tree::~tree()
{
	make_impty_tree(root);
}
bool tree::is_full()const
{
	node_tree *node;
	node=new node_tree;
	if(node!=NULL)
	{
		delete node;
		return false;
	}
	else
	{
		return true;
	}
}
int count_node(node_tree *node)
{
	if(node==NULL)
	{
		return 0;
	}
	else 
	{
		return (count_node(node->left)+count_node(node->right)+1);
	}
}
int tree::lengthis() const                            //return length 
{
	return(count_node(root));
}
void insert1(node_tree *&node, student st)
{
	tree treee;
	if(node==NULL)
	{
		node=new node_tree;
		node->right=NULL;
		node->left=NULL;
		node->info=st;
	}
	else if(st.compareto(node->info)==LESS)
	{
		insert1(node->left,st);
	}
	else if(st.compareto(node->info)==GREATER)
	{
		insert1(node->right,st);
	}
	else 
	{
		cout<<"item was found\n";
		st=get_data();
		treee.insert(st);
	}
}
void tree::insert(student st)
{
	insert1(root,st);
}
void get_predecessor(node_tree *node,student st)
{
	while(node->right!=NULL)
	{
		node=node->right;
	}
	st=node->info;
}
void delete_node(node_tree *node);

void delete_item(node_tree *node, student st)
{
	if(st.compareto(node->info)==LESS)
	{
		delete_item(node->left,st);
	}
	else if(st.compareto(node->info)==GREATER)
	{
		delete_item(node->right,st);
	}
	else if(st.compareto(node->info)==EQUAL)
	{
		delete_node(node);
	}
	else
	{
		cout<<" the item not found\n";
	}
}
void tree::delete1_item(student st)
{
	delete_item(root,st);
}
void delete_node(node_tree *node)
{
	student st1;
	node_tree *temp;
	temp=node;
	if(node->left==NULL)
	{
		node=node->right;
		delete temp;
	}
	else if(node->right==NULL)
	{
		node=node->left;
		delete temp;
	}
	else 
	{
		get_predecessor(node->left,st1);
		node->info=st1;
		delete_item(node->left,st1);
	}
}
void retrieve(node_tree *node,student st,bool &found)
{
	if(node==NULL)
	{
		found=false;
		cout<<" not found.\n\n";
	}
	else if(st.compareto(node->info)==LESS)
	{
		retrieve(node->left,st,found);
	}
	else if(st.compareto(node->info)==GREATER)
	{
		retrieve(node->right,st,found);
	}
	else if(st.compareto(node->info)==EQUAL)
	{
		st=node->info;
		cout<<" found & this his information \n";
		st.print();
		found=true;
	}
	else found=false;
}
void tree::retrieve_ITEM(student st,bool &found)
{
	retrieve(root,st,found);
}
void create_tree(tree &treee)
{
	treee.~tree();
	student st;
	node_tree *node;
	node=new node_tree;
	char more_data='y';
	while(more_data=='y')
	{
		st=get_data();
		if(!treee.is_full())
		{
			treee.insert(st);
		}
		cout<<"enter more data ? y = yes , n = no .\n your answer : ";
		cin>>more_data;
		more_data=(more_data=='Y'?'y':more_data);
	}
}
void print_tree(node_tree *node)
{
	if(node!=NULL)
	{
		print_tree(node->left);
		node->info.print();
		print_tree(node->right);
	}
}

void tree::print()
{
	print_tree(root);
}

void copy_tree1(node_tree *copy,node_tree *original)
{
	if(original==NULL)
	{
		copy=NULL;
	}
	else
	{
		copy=new node_tree;
		copy->info=original->info;
		copy_tree1(copy->left,original->left);
		copy_tree1(copy->right,original->right);
	}
}
void tree::copy_tree(tree &copy)
{
	copy_tree1(copy.root,root);
}
void main()
{
	char choose;   student st;  int length;  int p; bool found;
		char binary_search_tree='y'; 
		char suring;
		tree treee , copytree;
		cout<<"\n\n\t\t****** a binary search tree form ****\n\n";
			while(binary_search_tree=='y')
			{
			    cout<<"\t choose the operation that you want to do it :-\n\n";
				cout<<" 1- create tree from starting.\n\n";
			    cout<<" 2- insert new item.\n\n";
			    cout<<" 3- delete item from tree.\n\n";
			    cout<<" 4- search for item in the tree.\n\n";
			    cout<<" 5- formate the tree.\n\n";
			    cout<<" 6- print tree.\n\n";
			    cout<<" 7- knowing the number of the student in the tree.\n\n";
				cout<<" 8- to back to tha last bage. \n \n ";
				cout<<" your answer :   ";
			    cin>>choose;
				system("cls");
				cout<<endl;
			    switch(choose)
				{
				case'1':
	              create_tree(treee);
				    break;
				case'2':
					st=get_data();
					treee.insert(st);
					break;
				case'3':
				  cout<<"enter the id for this student that you want to delete it .\n";
                  cin>>p;
				  st.intialize(p," ");
				  cout<<"are you sure deleting this student that has id = "<<p;
				  cout<<"    y=yes ,n=no .\n your answer : ";
				  cin>>suring;
				  suring=(suring=='Y'?'y':suring);
				  if(suring=='y')
					{
						treee.delete1_item(st);
						cout<<"tree after deleting the item\n";
						treee.print();
					}
				    break;
				case'4':
					cout<<"enter the id for the student that you need search fot him .\n";
					cin>>p;
					st.intialize(p," ");
					treee.retrieve_ITEM(st,found);
				    break;
				case'5':
					cout<<"are you sure formating the tree. y = yes , n = no .\n your answer : ";
					cin>>suring;
					suring=(suring=='Y'?'y':suring);
					if(suring=='y')
					{
						treee.~tree();
						cout<<"tree is Impty now\n";
					}
				    break;
				case'6':
					length=treee.lengthis();
					if(length==0)
					{
						cout<<"list is Impty\n\n";
					}
					else
					{	
						treee.print();
					}
				    break;
				case'7':
					cout<<"the tree has ( ";
					cout<<treee.lengthis();
					cout<<" ) of students.\n\n";
					break;
				case'8':
					treee.copy_tree(copytree);
					cout<<"the tree is copied and this it's elements\n";
					copytree.print();
					break;
				}
				cout<<"do another operation ?\n: y=yes, n=no ";
		        cin>>binary_search_tree;
				binary_search_tree=(binary_search_tree=='Y'?'y':binary_search_tree);
				system("cls");
			}
		
}