Thursday, 7 August 2014

C++: Binary search tree(bst)

//============================================================================
// Name        : Tree.cpp
// Author      : Parashar
// Version     : 1.00
// Copyright   : Do not try this at home ;p
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

class node
{
public:
    int data;
    node *left;
    node *right;
};

class tree
{
public:
    node *root,*n;
public:
    tree();
    void create();
    void insert(node*,node*);
    void inorder(node*);
    void preorder(node*);
    void postorder(node*);
    void search(node*);
};

tree::tree()
{
    root=NULL;
}

void tree::search(node *temp)
{
    int key;
    temp=root;
    node *parent;
    cout<<"enter the key u wanna search";
    cin>>key;

int found=0;
    do
    {
        if(temp->data==key)
        {
        cout<<"key found  ";
        cout<<temp->data<<" is present"<<endl;
        found=1;
        }
        else
        {
            if(temp->data>key)
            {
                parent=temp;
                temp=temp->left;
            }
            else
            {
                parent=temp;
                temp=temp->right;
            }
        }

    }while(found==0);
}

void tree::create()
{
    char key;
    do
    {
    n=new node;
    n->left=NULL;
    n->right=NULL;
    cout<<"enter a value for node";
    cin>>n->data;
    if(root==NULL)
    {
        root=n;
    }
    else
    {
        insert(root,n);
    }
    cout<<"do you want to enter more nodes?"<<endl<<"if yes press 'y' else 'n'";
    cin>>key;
    }while(key=='y'||key=='Y');
}

void tree::insert(node *root,node *n)
{
    if(n->data<root->data)     //to insert an element in the left side
    {
        if(root->left==NULL)  //if left element is empty
        {
            root->left=n;
        }
        else            //if left element is not empty
        {
            insert(root->left,n);

        }
    }

    if(n->data>root->data)  //for right side
        {
            if(root->right==NULL)
            {
                root->right=n;
            }
            else
            {
                insert(root->right,n);

            }
        }
}

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

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

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


int main()
{
    int ch;
    cout << "!!!Made by PARASHAR!!!" << endl; // prints !!!Made by PARASHAR!!!
    tree t;
    do
    {
        cout<<"Program for TREE traversal"<<endl;
        cout<<"1)CTREATE tree"<<endl;
        cout<<"2)ADD a node"<<endl;
        cout<<"3)INORDER"<<endl;
        cout<<"4)PREORDER"<<endl;
        cout<<"5)POSTORDER"<<endl;
        cout<<"6)SEARCH"<<endl;
        cout<<"7)EXIT"<<endl;
        cout<<"Enter your choice"<<endl;
        cin>>ch;
        switch(ch)
        {
        case 1:
            t.create();
            break;
        case 2:
            t.create();
                    break;
        case 3:
            t.inorder(t.root);
                    break;
        case 4:
            t.preorder(t.root);
                    break;
        case 5:
            t.postorder(t.root);
                    break;
        case 6:
            t.search(t.root);
        }
    }while(ch<7);

    return 0;
}

//tnx for using code from www.parazhar.blogspot.in

No comments:

Post a Comment