Wednesday, September 25, 2013

binary search tree

The following is a link list implementation of BST I found on net,
I have made some changes to it if you found any error inform me I will fix it.

#include
using namespace std;

class BinarySearchTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           int data;
        };
        tree_node* root;
    public:
        BinarySearchTree()
        {
           root = NULL;
        }
        bool isEmpty() const { return root==NULL; }
        void print_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(int);
        void remove(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
    tree_node* temp = new tree_node;
    tree_node* parent;
    temp->data = d;
    temp->left = NULL;
    temp->right = NULL;
    parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = temp;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* current;
    current = root;
    // Find the Node's parent
    while(current)
    {
        parent = current;
        if(temp->data > current->data) current = current->right;
        else current = current->left;
    }

    if(temp->data < parent->data)
       parent->left = temp;
    else
       parent->right = temp;
  }
}

void BinarySearchTree::remove(int d)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<        return;
    }
    tree_node* current;
    tree_node* parent;
    current = root;
    while(current != NULL)
    {
         if(current->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = current;
             if(d>current->data) current = current->right;
             else current = current->left;
         }
    }
    if(!found)
    {
        cout<<" Data not found! "<<"\n";
        return;
    }


// 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
    {
       if(current->left == NULL && current->right != NULL)// right child present, no left child
       {
           if(parent->left == current)
           {
             parent->left = current->right;
             delete current;
           }
           else
           {
             parent->right = current->right;
             delete current;
           }
       }
       else  // left child present, no right child
       {
          if(parent->left == current)
           {
             parent->left = current->left;
             delete current;
           }
           else
           {
             parent->right = current->left;
             delete current;
           }
       }
     return;
    }

if( current->left == NULL && current->right == NULL) //We're looking at a leaf node
    {
        if(parent->left == current) parent->left = NULL;
        else parent->right = NULL;
delete current;
return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (current->left != NULL && current->right != NULL)
    {
        tree_node* chkright;
        chkright = current->right;
        if((chkright->left == NULL) && (chkright->right == NULL))
        {
            current->data = chkright->data;
            delete chkright;
            current->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((current->right)->left != NULL)
            {
                tree_node* leftcurr;
                tree_node* leftcurrp;
                leftcurrp = current->right;
                leftcurr = (current->right)->left;
                while(leftcurr->left != NULL)
                {
                   leftcurrp = leftcurr;
                   leftcurr = leftcurr->left;
                }
current->data = leftcurr->data;
                delete leftcurr;
                leftcurrp->left = NULL;
           }
           else
           {
               tree_node* temp;
               temp = current;
               current = current->right;
               delete temp;
           }

        }
return;
    }

}

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

void BinarySearchTree::print_preorder()
{
  preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}

void BinarySearchTree::print_postorder()
{
  postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<data<<" ";
    }
    else return;
}

int main()
{
    BinarySearchTree b;
    int ch,tmp,tmp1;
    do
    {
       cout<       cout<<" Binary Search Tree Operations "<<"\n";
       cout<<" ----------------------------- "<<"\n";
       cout<<" 1. Insertion/Creation "<<"\n";
       cout<<" 2. In-Order Traversal "<<"\n";
       cout<<" 3. Pre-Order Traversal "<<"\n";
       cout<<" 4. Post-Order Traversal "<<"\n";
       cout<<" 5. Removal "<<"\n";
       cout<<" 6. Exit "<<"\n";
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<                    cout<<" In-Order Traversal "<<"\n";
                    cout<<" -------------------"<<"\n";
                    b.print_inorder();
                    break;
           case 3 : cout<                    cout<<" Pre-Order Traversal "<<"\n";
                    cout<<" -------------------"<<"\n";
                    b.print_preorder();
                    break;
           case 4 : cout<                    cout<<" Post-Order Traversal "<<"\n";
                    cout<<" --------------------"<<"\n";
                    b.print_postorder();
                    break;
           case 5 : cout<<" Enter data to be deleted : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 6 : cout<<"Exiting";
                    return 0;
                    break;
            default : cout<<"Enter valid choice";
                        break;
       }
   
    }while(ch!=6);
}