TREE.CPP

#include<iostream>
using namespace std;

class node
{
	int info;
	node *next;
	node* previous;
public:
	node(int m = 0 )	 	
	{
		info = m;
		next = NULL;
		previous = NULL;
	}

	void setdata(int m)
	{
		info = m;
	}
	
	node* getnext()
	{
		return next;
	}

	void setnext(node* p)
	{
		next = p;
	}
		
	void setprevious(node* p)
	{
		previous = p;
	}
	
	node* getprevious()
	{
		return previous;
	}
	
	int getdata()
	{
		return info;
	}
};

class tree
{
	node* start;
public:
	tree()
	{
		start = NULL;
	}
	
	void add_node(int s)	 
	{
		node *temp = new node(s);
		if(start == NULL){start = temp;return;}
				
		node* search=start;
		node* papa;
		while(search != NULL)
		{
			papa = search;
			if(temp->getdata() < search->getdata())
			{
				search = search->getprevious();
				continue;
			}
			search = search->getnext();
		}
		
 		if(temp->getdata() < papa->getdata())
		{
			papa->setprevious(temp);
			return;
		}
			papa->setnext(temp);
			return;
	}	


	void deletion(int m )
	{
		if(start==NULL)
		{
			cout<<"OOPS!  THERE IS NO ITEM IN THIS LIST."<<endl;
			return;
		}		

		node* search=start;
		node* last = start;
		
		while(search!=NULL)
		{
					
			if(search->getdata()==m)
			{
				
				if(search->getnext() != NULL && search->getprevious() != NULL)
				{
	
					node* upper = last;
					node* traverse = search->getnext();
					while(traverse->getprevious() != NULL)
					{
						upper = traverse;
						traverse = traverse->getprevious();
					}
					
					if(upper != last)
					{
						upper->setprevious(traverse->getnext());
					}
					
					if(search == start){}
					else if(m < last->getdata()){last->setprevious(traverse);}
					else{last->setnext(traverse);}
					
					traverse->setprevious(search->getprevious());
					
					if(upper != last)
					{
						traverse->setnext(search->getnext());
					}
					
					if(search == start){start=traverse;}
					cout<<"\t"<<m<<" DELETED."<<endl;
					delete search;
					return;
					
				}
				
				if(search == start)
				{
					if(search->getnext() != NULL)
					{
					node* upper = start;
					node* traverse = start->getnext();
					while(traverse->getprevious() != NULL)
					{
						upper = traverse;
						traverse = traverse->getprevious();
					}
						if(traverse != start->getnext())
						{
							upper->setprevious(traverse->getnext());
							traverse->setnext(start->getnext());
						} 
						start = traverse;
						
				}
					else if(start->getprevious() != NULL)
					{
						start = start->getprevious();
					}
					else
					{
						start =NULL;
					}
					delete search;
					return;
				}
				
				if(m < last->getdata())
				{
					if(search->getnext()==NULL)
					{last->setprevious(search->getprevious());}
					else
					{last->setprevious(search->getnext());}
				}
				else
				{
					if(search->getnext()==NULL)
					{last->setnext(search->getprevious());}
					else
					{last->setnext(search->getnext());}
				}
					cout<<"\t"<<m<<" DELETED."<<endl;
					delete search;
					return;
		 	}
					
			last = search;
			
			if(m < search->getdata()){search = search->getprevious();}
			else
				search = search->getnext();
		}
		
			cout<<"NODE NOT FOUND"<<endl;
	}

	void rootfirst(node * dis )		
	{
				if(dis!= NULL)
				{
					cout<<dis->getdata()<<endl;
					rootfirst(dis->getprevious());
					rootfirst(dis->getnext());
				}
	}
	
	void rootin(node * dis)
	{
				if(dis!= NULL)
				{
					rootin(dis->getprevious());
					cout<<dis->getdata()<<endl;
					rootin(dis->getnext());
				}
	}	
	
	void rootlast(node * dis)	
	{		
				if(dis!= NULL)
				{
					rootlast(dis->getprevious());
					rootlast(dis->getnext());
					cout<<dis->getdata()<<endl;					
				}
	}
	
	void truncate(node * dis)	
	{		
				if(dis!= NULL)
				{
					rootlast(dis->getprevious());
					rootlast(dis->getnext());
					delete dis;					
				}
				start = NULL;
				cout<<"DATABASE TRUNCATED."<<endl;
	}
	
	void display(int option)
	{
		if(start==NULL){cout<<"LIST EMPTY"<<endl;return;}
		node* dis=start;
		switch(option)
		{
			case 3:
				rootfirst(start);
				break;
			case 4:
				rootin(start);
				break;
			case 5:
				rootlast(start);
				break;
			case 9:
				truncate(start);
				break;
			default:
				cout<<"BAD CHOICE___  GO HOME & SLEEP...  FURRRRRRRRRRRRRRRRRRR"<<endl;
		}
	}
	
	void search(int value)
	{
		node* khoj=start;
		while(khoj!=NULL)
		{
			if(value==khoj->getdata())
			{
			
	cout<<"FOUND  ";
				int count = 0;
				do
				{
					if(khoj->getdata()==value)
					{
						khoj = khoj->getnext();
						count++;
					}
					else
						khoj = khoj->getprevious();
					}while(khoj != NULL);
				cout<<count<<"  TIMES"<<endl;
				return;
			}
			if(value < khoj->getdata())
			{khoj = khoj->getprevious();}
			else
			khoj = khoj->getnext();
		}
		cout<<"THIS DATA IS NOT IN LIST."<<endl;
	}
	int getroot()
	{
		if(start == NULL){ cout<<"LIST EMPTY.";return 0;}
		return start->getdata();
	}
};

int main()
{
	int chak; 
	tree list;
	tree list7;
	{
		list.add_node(35);
		list.add_node(45);
		list.add_node(15);
		list.add_node(3);
		list.add_node(29);
		list.add_node(15);
		list.add_node(1);
		list.add_node(90);
	}
	
  do 
  {		
	cout<<endl;
	cout<<"1.INSERT A DATA.\n2.INSERT MULTIPLE DATA ENTRY.\n3.TRAVERSE ROOT FIRST (PREORDER).\n4.BETWEEN CHILD (INORDER).\n5.ROOT LAST (POSTORDER).\n6.SEARCH DATA.\n7.ROOT VALUE\n8.DELETE A SPECIFIC DATA\n9.TRUNCATE ENTIRE LIST.\n10.EXIT.\n";
   	cout<<endl;
	cout<<"ENTER YOUR CHOICE FROM THE ABOVE."<<endl;
	int data;
	cin>>chak;
	cout<<endl;
	switch(chak)
	{
		case 1:
		case 2:
			{
				int how_many = 1;
				if(chak==2)
				{
					cout<<"HOW MANY ELEMENTS DO YOU WANT TO ENTER."<<endl;
					cin>>how_many;
					cout<<"ENTER DATA ELEMENTS ONE BY ONE."<<endl;
				}
				else
				{cout<<"ENTER A DATA ENTERY"<<endl;}
				for(int i = 0; i < how_many; i++)
				{
					cin>>data;
					list.add_node(data);
				}
				break;
			}
		case 3:
		case 4:
		case 5:
		case 9:
			{
				list.display(chak);
				break;
			}
		case 6:
			{
				cout<<"ENTER DATA VALUE TO BE SEARCHED."<<endl
				;cin>>data;
				list.search(data);
				break;
			}
		case 7:
				cout<<list.getroot()<<endl;
				break;
		case 8:
				cout<<"ENTER DATA VALUE TO BE DELETED."<<endl;
				cin>>data;
				list.deletion(data);
				break;
		case 10:
			break;
		default:
				cout<<"BAD CHOICE. TRY AGAIN.\n";
			
	}
   }while(chak != 10);
	cout<<endl;	
	return 0;
}