# include <iostream.h> # include <conio.h> /**************************************************************************/ //------------------------------- Tree ---------------------------------// /**************************************************************************/ class Tree { private: int data; Tree *Left; Tree *Right; public: Tree *Root_node; Tree *Location; Tree *Parent; Tree( ) { Root_node=NULL; } Tree* insert_element(Tree*,int); // These two functions are used to find the max tree depth int get_tree_depth(Tree*); void find_tree_depth(Tree*,int,int&); void search_element(int); void delete_element(int); void delete_element_with_0_or_1_child( ); void delete_element_with_2_child( ); void print_tree_in_post_order(Tree*); void print_tree_in_pre_order(Tree*); void print_tree_in_in_order(Tree*); void show_working( ); }; //-------------------------- insert_element( ) ------------------------// Tree* Tree::insert_element(Tree *root,int data) { if(root==NULL) { Tree *Temp; Temp=new Tree; Temp->data=data; root=Temp; root->Left=NULL; root->Right=NULL; cout<<\"\\n\\n\\t *** \"<<data<<\" is inserted into the Tree.\"<<endl; cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } else { Parent=root; if(data>root->data) { if(root->Right==NULL) root->Right=insert_element(root->Right,data); else insert_element(root->Right,data); } else { if(root->Left==NULL) root->Left=insert_element(root->Left,data); else insert_element(root->Left,data); } } return root; } //--------------------- print_tree_in_pre_order( ) --------------------// void Tree::print_tree_in_pre_order(Tree *root) { if(root==NULL) { } else { cout<<\"\\t \"<<root->data<<endl; if(root->Left!=NULL) print_tree_in_pre_order(root->Left); if(root->Right!=NULL) print_tree_in_pre_order(root->Right); } } //--------------------- print_tree_in_post_order( ) -------------------// void Tree::print_tree_in_post_order(Tree *root) { if(root==NULL) { } else { if(root->Left!=NULL) print_tree_in_post_order(root->Left); if(root->Right!=NULL) print_tree_in_post_order(root->Right); cout<<\"\\t \"<<root->data<<endl; } } //----------------------- print_tree_in_in_order( ) -------------------// void Tree::print_tree_in_in_order(Tree *root) { if(root==NULL) { } else { if(root->Left!=NULL) print_tree_in_in_order(root->Left); cout<<\"\\t \"<<root->data<<endl; if(root->Right!=NULL) print_tree_in_in_order(root->Right); } } //------------------------- search_element( ) -------------------------// void Tree::search_element(int Search_key) { int depth=1; int left_right=0; Tree *Pointer=NULL; Tree *Save=NULL; Location=NULL; Parent=NULL; if(Root_node==NULL) { Location=NULL; Parent=NULL; } else if(Search_key==Root_node->data) { Location=Root_node; Parent=NULL; depth=1; } else { if(Search_key<Root_node->data) { Pointer=Root_node->Left; left_right=1; } else { Pointer=Root_node->Right; left_right=2; } Save=Root_node; while(Pointer!=NULL) { depth+=1; if(Search_key==Pointer->data) { Location=Pointer; Parent=Save; break; } else if(Search_key<Pointer->data) { Save=Pointer; Pointer=Pointer->Left; } else if(Search_key>Pointer->data) { Save=Pointer; Pointer=Pointer->Right; } } } if(Location==NULL) { Parent=NULL; cout<<\"\\n\\n\\n\\n\\n\\t *** \"<<Search_key<<\" is not found in the Tree. \"<<endl; } else if(Location!=NULL) { if(left_right==0) cout<<\"\\n\\n\\n\\t *** \"<<Search_key<<\" is the Root Node.\"<<endl; else if(left_right==1) cout<<\"\\n\\n\\n\\t *** \"<<Search_key<<\" lies at the Left side of the Root Node \"; else if(left_right==2) cout<<\"\\n\\n\\n\\t *** \"<<Search_key<<\" lies at the Right side of the Root Node \"; if(left_right) cout<<\"and at the depth level \"<<depth<<endl; } cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } //--------------- delete_element_with_0_or_1_child( ) -----------------// void Tree::delete_element_with_0_or_1_child( ) { Tree *Child; if(Location->Left==NULL && Location->Right==NULL) Child=NULL; else if(Location->Left!=NULL) Child=Location->Left; else Child=Location->Right; if(Parent!=NULL) { if(Location==Parent->Left) Parent->Left=Child; else Parent->Right=Child; } else Root_node=Child; } //------------------- delete_element_with_2_child( ) ------------------// void Tree::delete_element_with_2_child( ) { Tree *Pointer=Location->Right; Tree *Save=Location; Tree *Sucessor; Tree *Parent_sucessor; while(Pointer->Left!=NULL) { Save=Pointer; Pointer=Pointer->Left; } Sucessor=Pointer; Parent_sucessor=Save; Tree *temp_loc=Location; Tree *temp_par=Parent; Location=Sucessor; Parent=Parent_sucessor; delete_element_with_0_or_1_child( ); Location=temp_loc; Parent=temp_par; if(Parent!=NULL) { if(Location==Parent->Left) Parent->Left=Sucessor; else Parent->Right=Sucessor; } else Root_node=Sucessor; Sucessor->Left=Location->Left; Sucessor->Right=Location->Right; } //------------------------ delete_element( ) --------------------------// void Tree::delete_element(int delete_key) { search_element(delete_key); if(Root_node==NULL) cout<<\"\\n\\n\\n\\t *** Error : Tree is empty. \\n\"<<endl; else if(Location==NULL) cout<<\"\\n\\n\\n\\t *** \"<<delete_key<<\" does not exists in the tree \\n\"<<endl; else { if(Location->Right!=NULL && Location->Left!=NULL) delete_element_with_2_child( ); else delete_element_with_0_or_1_child( ); cout<<\"\\n\\n\\n\\t *** \"<<delete_key<<\" is deleted from the Tree.\"<<endl; cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } } //------------------------ get_tree_depth( ) --------------------------// int Tree::get_tree_depth(Tree *root) { int depth=0; int temp=-1; find_tree_depth(root,temp,depth); return depth; } //------------------------ get_tree_depth( ) --------------------------// void Tree::find_tree_depth(Tree *root,int temp,int& depth) { if(root==NULL) { } else { temp++; if(temp>depth) depth=temp; if(root->Left!=NULL) find_tree_depth(root->Left,temp,depth); if(root->Right!=NULL) find_tree_depth(root->Right,temp,depth); } } //-------------------------- show_working( ) --------------------------// void Tree::show_working( ) { char Key=NULL; do { clrscr( ); gotoxy(5,5); cout<<\"******** Implementation of Linked List as a Binary Search Tree ********\"<<endl; gotoxy(10,8); cout<<\"Select one of the listed operation :\"<<endl; gotoxy(15,10); cout<<\"- Press \\\'I\\\' to Insert a value\"<<endl; gotoxy(15,12); cout<<\"- Press \\\'D\\\' to Delete a value\"<<endl; gotoxy(15,14); cout<<\"- Press \\\'P\\\' to Print the values in In-Order\"<<endl; gotoxy(15,16); cout<<\"- Press \\\'Q\\\' to Print the values in Pre-Order\"<<endl; gotoxy(15,18); cout<<\"- Press \\\'R\\\' to Print the values in Post-Order\"<<endl; gotoxy(15,20); cout<<\"- Press \\\'T\\\' to Print the max. Tree Depth\"<<endl; gotoxy(15,22); cout<<\"- Press \\\'E\\\' to Exit\"<<endl; Input: gotoxy(10,26); cout<<\" \"; gotoxy(10,26); cout<<\"Enter your Choice : \"; Key=getche( ); if(int(Key)==27 || Key==\'e\' || Key==\'E\') break; else if(Key==\'i\' || Key==\'I\') { int item; cout<<\"\\n\\n\\n\\n\\n\\t Enter the value to insert into Tree : \"; cin>>item; if(Root_node==NULL) Root_node=insert_element(Root_node,item); else insert_element(Root_node,item); } else if(Key==\'d\' || Key==\'D\') { int item; cout<<\"\\n\\n\\n\\n\\n\\t Enter the value to delete from Tree : \"; cin>>item; delete_element(item); } else if(Key==\'s\' || Key==\'S\') { int item; cout<<\"\\n\\n\\n\\n\\n\\t Enter the value to search from Tree : \"; cin>>item; search_element(item); } else if(Key==\'p\' || Key==\'P\') { if(Root_node!=NULL) cout<<\"\\n\\n\\n\\n\\n\\t Values of Tree in In-Order are : \\n\"<<endl; else cout<<\"\\n\\n\\n\\n\\n\\t *** Nothing to show. \"<<endl; print_tree_in_in_order(Root_node); cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } else if(Key==\'q\' || Key==\'Q\') { if(Root_node!=NULL) cout<<\"\\n\\n\\n\\n\\n\\t Values of Tree in Pre-Order are : \\n\"<<endl; else cout<<\"\\n\\n\\n\\n\\n\\t *** Nothing to show. \"<<endl; print_tree_in_pre_order(Root_node); cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } else if(Key==\'r\' || Key==\'R\') { if(Root_node!=NULL) cout<<\"\\n\\n\\n\\n\\n\\t Values of Tree in Post-Order are : \\n\"<<endl; else cout<<\"\\n\\n\\n\\n\\n\\t *** Nothing to show. \"<<endl; print_tree_in_post_order(Root_node); cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } else if(Key==\'t\' || Key==\'T\') { if(Root_node!=NULL) cout<<\"\\n\\n\\n\\n\\n\\t Tree Depth = \"<<get_tree_depth(Root_node)<<endl; else cout<<\"\\n\\n\\n\\n\\n\\t *** Nothing to show. \"<<endl; cout<<\"\\n\\n\\n\\t\\t Pres any key to return to Menu. \"; getch( ); } else goto Input; } while(1); } //---------------------------- main( ) --------------------------------// int main( ) { Tree tree_obj; tree_obj.show_working( ); return 0; }