Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Object Oriented ProgrammingRSS Feeds

Program of Binary Search Tree Operations

Posted By: Easy Tutor     Category: C++ Programming     Views: 102098

Write a Program of Binary Search Tree Operations.

Code for Program of Binary Search Tree Operations in C++ Programming


#include <iostream.h>
#include <process.h> //for exit(1)
#include <conio.h>

struct node{
    int data;
    struct node *left;
    struct node *right;
};

class BST{
    public:
    node *tree;
    BST(){
        tree=NULL;
    }
    void createTree(node **,int item);    //For Building Treevoid preOrder(node *);     //For Tree Traversalvoid inOrder(node *);
    void postOrder(node *);

    void determineHeight(node *,int *);
    int totalNodes(node *);
    int internalNodes(node *); //no. of non-leaf nodesint externalNodes(node *); //no. of leaf nodes.void removeTree(node **); //Remove tree from memory.

    node **searchElement(node **,int);
    void findSmallestNode(node *);
    void findLargestNode(node *);
    void deleteNode(int);
};


//it is used for inseting an single element in//a tree, but if calls more than once will create tree.void BST :: createTree(node **tree,int item){
    if(*tree == NULL){
        *tree = new node;
        (*tree)->data = item;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
    }
    else{
        if( (*tree)->data > item)
            createTree( &((*tree)->left),item);
        else
            createTree( &((*tree)->right),item);
    }
}


void BST :: preOrder(node *tree){
    if( tree!=NULL){
        cout<<"   "<< tree->data;
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

void BST :: inOrder(node *tree){
    if( tree!=NULL){
        inOrder( tree->left);
        cout<<"   "<< tree->data;
        inOrder(tree->right);
    }
}


void BST :: postOrder(node *tree){
    if( tree!=NULL){
        postOrder( tree->left);
        postOrder( tree->right);
        cout<<"   "<<tree->data;
    }
}


void BST :: determineHeight(node *tree, int *height){
    int left_height, right_height;
    if( tree == NULL)
        *height = 0;
    else{
        determineHeight(tree->left, &left_height);
        determineHeight(tree->right, &right_height);
        if( left_height > right_height)
            *height = left_height + 1;
        else
            *height = right_height + 1;
    }
}


int BST :: totalNodes(node *tree){
    if( tree == NULL)
        return 0;
    elsereturn( totalNodes(tree->left) + totalNodes(tree->right) + 1 );
}

int BST :: internalNodes(node *tree){
    if( (tree==NULL)  || (tree->left==NULL  && tree->right==NULL))
        return 0;
    elsereturn( internalNodes(tree->left) + internalNodes(tree->right) + 1 );
}

int BST :: externalNodes(node *tree){
    if( tree==NULL )
        return 0;
    elseif( tree->left==NULL  && tree->right==NULL)
        return 1;
    elsereturn( externalNodes(tree->left) + externalNodes(tree->right));
}

void BST :: removeTree(node **tree){
    if( (*tree) != NULL){
        removeTree( &(*tree)->left );
        removeTree( &(*tree)->right );
        delete( *tree );
    }
}

node ** BST :: searchElement(node **tree, int item){
    if( ((*tree)->data == item) || ( (*tree) == NULL) )
        return tree;
    elseif( item < (*tree)->data)
        return searchElement( &(*tree)->left, item);
    elsereturn searchElement( &(*tree)->right, item);
}

void BST :: findSmallestNode(node *tree){
    if( tree==NULL || tree->left==NULL)
        cout<< tree->data;
    else
        findSmallestNode( tree->left);
}


//Finding In_order Successor of given node..//for Delete Algo.
node * find_Insucc(node *curr)
{
    node *succ=curr->right; //Move to the right sub-tree.if(succ!=NULL){
        while(succ->left!=NULL)    //If right sub-tree is not empty.
            succ=succ->left; //move to the left-most end.
    }
    return(succ);
}


void BST :: findLargestNode(node *tree){
    if( tree==NULL || tree->right==NULL)
        cout<<tree->data;
    else
        findLargestNode(tree->right);
}


void BST :: deleteNode(int item){
    node *curr=tree,*succ,*pred;
    int flag=0,delcase;
    //step to find location of nodewhile(curr!=NULL && flag!=1)
    {
        if(item < curr->data){
            pred = curr;
            curr = curr->left;
        }
        elseif(item > curr->data){
            pred = curr;
            curr = curr->right;
        }
        else{ //curr->data = item
            flag=1;
        }
    }

    if(flag==0){
        cout<<"\nItem does not exist : No deletion\n";
        getch();
        goto end;
    }

    //Decide the  case of deletionif(curr->left==NULL && curr->right==NULL)
        delcase=1; //Node has no childelseif(curr->left!=NULL && curr->right!=NULL)
        delcase=3; //Node contains both the childelse
        delcase=2; //Node contains only one child//Deletion Case 1if(delcase==1){
        if(pred->left == curr) //if the node is a left child
            pred->left=NULL; //set pointer of its parentelse
            pred->right=NULL;
        delete(curr); //Return deleted node to the memory bank.
    }

    //Deletion Case 2if(delcase==2){
        if(pred->left==curr){ //if the node is a left childif(curr->left==NULL)
                pred->left=curr->right;
            else
                pred->left=curr->left;
        }
        else{ //pred->right=currif(curr->left==NULL)
                pred->right=curr->right;
            else
                pred->right=curr->left;
        }
        delete(curr);
    }

    //Deletion case 3if(delcase==3){
        succ = find_Insucc(curr); //Find the in_order successor//of the node.int item1 = succ->data;
        deleteNode(item1);  //Delete the inorder successor
        curr->data = item1; //Replace the data with the data of//in order successor.
    }
end:
}



void main(){
    BST obj;
    int choice;
    int height=0,total=0,n,item;
    node **tmp;

    while(1){
        clrscr();
        cout<<"*****BINARY SEARCH TREE OPERATIONS*****\n\n";
        cout<<"--Binary Tree and Binary Search Tree common operations--\n";
        cout<<"1) Create Tree\n";
        cout<<"2) Traversal\n";
        cout<<"3) Height of Tree\n";
        cout<<"4) Total Nodes\n";
        cout<<"5) Internal Nodes \n";
        cout<<"6) External Nodes \n";
        cout<<"7) Remove Tree\n";
        cout<<"\n--Only Binary Search Tree Operations--\n";
        cout<<"8)  Insert Node\n";
        cout<<"9)  Search Node\n";
        cout<<"10) Find Smallest Node\n";
        cout<<"11) Find Largest Node\n";
        cout<<"12) Delete Node\n";
        cout<<"13) Exit\n";
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice){
            case 1 : //Create Tree
                cout<<"\n\n--Creating Tree--";
                cout<<"\nHow many nodes u want to enter : ";
                cin>>n;
                for(int i=0;i<n;i++){
                    cout<<"Enter value : ";
                    cin>>item;
                    obj.createTree(&obj.tree,item);
                }
                break;

            case 2 : //All Traversals
                cout<<"\n\nInorder Traversal : ";
                obj.inOrder(obj.tree);

                cout<<"\n\nPre-order Traversal : ";
                obj.preOrder(obj.tree);

                cout<<"\n\nPost-order Traversal : ";
                obj.postOrder(obj.tree);
                getch();
                break;

            case 3 : //Determining Height of Tree
                obj.determineHeight(obj.tree,&height);
                cout<<"\n\nHeight of Tree : "<<height;
                getch();
                break;

            case 4 : //Total nodes in a tree
                total=obj.totalNodes(obj.tree);
                cout<<"\n\nTotal Nodes : "<<total;
                getch();
                break;

            case 5 : //Internal nodes in a tree
                total=obj.internalNodes(obj.tree);
                cout<<"\n\nInternal Nodes : "<<total;
                getch();
                break;

            case 6 : //External nodes in a tree
                total=obj.externalNodes(obj.tree);
                cout<<"\n\nExternal Nodes : "<<total;
                getch();
                break;

            case 7 : //Remove Tree from memory
                obj.removeTree(&obj.tree);
                cout<<"\n\nTree is removed from Memory";
                getch();
                break;

            case 8 : //Inserting a node in a tree
                cout<<"\n\n--Inserting Node in a tree--\n";
                cout<<"Enter value : ";
                cin>>item;
                obj.createTree(&obj.tree,item);
                cout<<"\nItem is inserted\n";
                getch();
                break;

            case 9 : //Search element
                cout<<"\n\n--Search Element--\n";
                cout<<"Enter item to searched : ";
                cin>>item;
                &(*tmp) = obj.searchElement(&obj.tree,item);
                if( (*tmp) == NULL)
                    cout<<"\nSearch Element Not Found";
                else
                    cout<<"\nSearch Element was Found";
                getch();
                break;

            case 10 : //Find Smallest Node
                cout<<"\n\nSmallest Node is :  ";
                obj.findSmallestNode(obj.tree);
                getch();
                break;

            case 11 : //Find Largest Node
                cout<<"\n\nLargest Node is :  ";
                obj.findLargestNode(obj.tree);
                getch();
                break;

            case 12 : //Deleting a node from a tree
                cout<<"\n\n--Deleting a Node from a tree--\n";
                cout<<"Enter value : ";
                cin>>item;
                obj.deleteNode(item);
                break;

            case 13 : exit(1);
        }//end of switch
    }
}
  
Share: 

 
 

Didn't find what you were looking for? Find more on Program of Binary Search Tree Operations Or get search suggestion and latest updates.

Easy Tutor
Easy Tutor author of Program of Binary Search Tree Operations is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 

Other Interesting Articles in C++ Programming:


 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
Esa Habib from Indonesia Comment on: Jun 13
please help me ,,
there are errors in the code "& (* tmp) = obj.searchElement (& obj.tree, item);" ?

Ryo Yassino from United States Comment on: Dec 08
it doesn't work !! help

View All Comments