Pages

Program of Binary Search Tree in C++

#include<iostream>
using namespace std;

class bst
{
    struct node
    {
        int info;
        struct node *left,*right;
    }*root;
   
    public:
    bst()
    {
        root=NULL;
    }
    void create(int ele);
    void inorder(node *root);
    void preorder(node *root);
    void postorder(node *root);
    void del(int ele);
    void display();
};

void bst::create(int ele)
{
    node *temp=new node;
    node *p=root,*q;
    temp->info=ele;
    temp->left=temp->right=NULL;
    if(root==NULL)
    {
        root=temp;
        return;
    }
    while(p!=NULL)
    {
        q=p;
        if(p->info==ele)
        {
            cout<<"\nNode already exists";
            return;
        }
        if(p->info>ele)
            p=p->left;
        else
            p=p->right;
    }
    if(q->info>ele)
        q->left=temp;
    else
        q->right=temp;
}

void bst::inorder(node *root)
{
    if(root!=NULL)
    {
        inorder(root->left);
        cout<<root->info<<" ";
        inorder(root->right);
    }
   
}

void bst::preorder(node *root)
{
    if(root!=NULL)
    {
        cout<<root->info<<" ";
        inorder(root->left);       
        inorder(root->right);
    }
   
}

void bst::postorder(node *root)
{
    if(root!=NULL)
    {
        inorder(root->left);       
        inorder(root->right);
        cout<<root->info<<" ";
    }
   
}
void bst::display()
{
    cout<<"\nInorder\n";
    inorder(root);
    cout<<"\npreorder\n";
    preorder(root);
    cout<<"\npostorder\n";
    postorder(root);
}

void bst::del(int ele)
{
    node *p=root,*q=root;
    if(root==NULL)
    {
        cout<<"\nEmpty tree\n";
        return;
    }
    while(p!=NULL && p->info!=ele)
    {
        q=p;
        if(p->info<ele)
            p=p->right;
        else
            p=p->left;
    }
    if(p==NULL)
    {
        cout<<"\nElement not found\n";   
        return;   
    }
    if(p->left==NULL && p->right==NULL)    //Leaf node
    {
        if(q->info<ele)
            q->right=NULL;
        else
            q->left=NULL;   
        delete(p);       
    }
    if(p->left==NULL)
    {
   
    }           
}

main()
{
    bst b1;
    int i,ele;
    b1.create(50);
    b1.create(30);
    b1.create(40);
    b1.create(20);
    b1.create(100);
    b1.create(120);
    b1.create(70);

    b1.display();
    for(i=0;i<7;i++)
    {
        cout<<"\nEnter a number to delete=";
        cin>>ele;
        b1.del(ele);
        cout<<"\n\nAfter deleting "<<ele<<"\n";
        b1.display();
    }
}

No comments:

Post a Comment