C++ Programming Blog

 
 
 

Image

 # 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;
    }

    Related Post:
  1. Program to illustrate multiple inheritance

  2. Program to illustrate classes with inline functions

  3. Program to illustrate the multi-level inheritance

  4. Program to illustrate the role of destructor in classes

  5. Program to count number of words, lines and characters in given string

  6. Program to read marks of 10 students for 4 subjects and compute and display total marks and status of each student

  7. Program of Deapth First Search Traversal ( DFS )

  8. To parse a string using First and Follow algorithm and LL-1 parser

  9. Write a Program to create Numeric Triangle

  10. Program to convert points to rectangle coordinates and polar coordinates

  11. Program to estimate the value of First Derivative of the function at the given points from the given data using Central Difference Formula of order 4

  12. PROGRAM FOR PASS-I & PASS-II

  13. CREATING A CLASS ACCOUNTS FROM WHICH ARE DERIVED TWO CLASSES CURRENT AND SAVINGS AND THEN ASK THE USER FOR THE TYPE OF ACCOUNT HE WANTS TO CREATE

  14. Program to draw a line using Digital Differential Analyzer (DDA) Algorithm

  15. Program that take font and background color and text input from a user and display it in right aligned

  16. Program that provides facilities of calculator in c++

  17. Program to read a Non-Linear equation in one variable, then evaluate it using Bisection Method and display its kD accurate root

  18. Program to read a Non-Linear equation in one variable, then evaluate it using Modified False-Position Method and display its kD accurate root

  19. Program for using enum

  20. Program to illustrate the binary operator(+) overloading by creating a new object

 
 
Didn't find what you were looking for? Find more on Program to show find the maximum depth of a Binary Search Tree