Question

C++ : Implement the ordered list type using a pointer-based binary search tree.

The elements of the class's lists are integers, but it should be easy to change this type.

The class should implement the following operations on ordered lists of its element type:

• Initialize a list to be empty (the default constructor).
• A destructor that deletes the dynamic memory in the tree that represents a list.
• Re-initialize an existing list to be empty.
• Insert a value into a list, in the appropriate position. If the value is already present, the list is unchanged.
• Remove a value from a list. If the value is not present, the list is unchanged.
• Return the length of a list: the number of values it contains.
• Report whether or not a particular value is present in a list.
• Write out the values in a list, in order, to an output stream.

OTHER REQUIREMENTS

Use a typedef statement to specify the item type in the class's list type, so that the item type can be changed easily - From an integer-based list to a character-based list.

Consider whether functions associated with the class should be member functions, friend functions, or nonmember functions.

Answer 1

Code:-

#include<iostream>
#include<stdlib.h>
#include<conio.h>
using namespace std;
typedef struct BST
{
   int data;
   struct BST *left, *right;
}node;
class Binary_Tree
{
   public:
   void insert(node *root, node *new_node)
   {
       if (new_node->data < root->data)
       {  
           if (root->left == NULL)  
               root->left = new_node;  
           else  
               insert(root->left, new_node);  
       }  
       if (new_node->data > root->data)  
       {  
           if (root->right == NULL)  
               root->right = new_node;  
           else  
               insert(root->right, new_node);  
       }
   }
   public:
   node *search(node *root, int key, node **parent)
   {
       node *temp;
       temp = root;
       while (temp != NULL)
       {
           if (temp->data == key)
           {
               cout<<"\nThe Element "<<temp->data<<"is Present"<<endl;
               return temp;
           }
           *parent = temp;
           if (temp->data > key)
               temp = temp->left;
           else
               temp = temp->right;
       }
       return NULL;
   }
   public:
   void inorder(node *temp)
   {
       if (temp != NULL)
       {
           inorder(temp->left);
           cout<<"\t"<<temp->data;
           inorder(temp->right);
       }
   }
   public:
   node *get_node()
   {
       node *temp;
       temp = (node *) malloc(sizeof(node));
       temp->left = NULL;
       temp->right = NULL;
       return temp;
   }
};
int main()
{
   Binary_Tree obj;
   int option;
   char ans = 'N';
   int key;
   node *new_node, *root, *tmp, *parent;
   node *get_node();
   root = NULL;
   cout<<"\n ** Program For Binary Search Tree **\n"<<endl;
   while(1)
   {
       cout<<"\n1.Insert The Element";
       cout<<"\n2.Search The Element";
       cout<<"\n3.Print Tree in inorder";
       cout<<"\n4.Exit";
       cout<<"\nSelect your choice :";
       cin>>option;
       switch (option)
       {
           case 1:
           do
           {
               new_node = obj.get_node();
               cout<<"\nEnter The Element: ";
               cin>>new_node->data;
               if (root == NULL)
                   root = new_node;
               else
                   obj.insert(root, new_node);
               cout<<"\nDo you Want To insert More Elements?(y/n)";
               ans = getch();
           }
           while (ans == 'y');
               break;
           case 2:
           cout<<"\nEnter Element to be searched: ";
           cin>>key;
           tmp=obj.search(root, key, &parent);
           cout<<"\nParent of node "<<tmp->data<<" is "<<parent->data<<endl;
           break;
           case 3:
           if (root == NULL)
           {
               cout<<"\nTree Is Empty"<<endl;
           }
           else
           {
               cout<<"\nThe Inorder display: ";
               obj.inorder(root);
           }
           break;
           case 4:
           exit(0);
       }
   }
}

Code Screenshots:-

Output:-

Please UPVOTE thank you...!!!