Thursday, October 27, 2016

Binary tree implementation (search,preorder,postorder,inorder,insert operations)

There's various way to implement but i have implemented following below systems.

#include<bits/stdc++.h>
using namespace std;

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

};

struct node* create_node(int data)
{
  struct node* node1 = new node();
    node1->data=data;
    node1->left=NULL;
    node1->right=NULL;

    return node1;
}

struct node* insert(struct node* root, int data)
{
    if(root==NULL)
    {
        root=create_node(data);
    }
    else if(data<root->data)
    {
        root->left=insert(root->left,data);
    }
    else
    {
        root->right=insert(root->right,data);
    }

    return root;
}

void pre_order(struct node* n)
{
    if(n)
    {
        cout<<n->data<<" ";
        pre_order(n->left);
        pre_order(n->right);
    }
}

void post_order(struct node* n)
{
    if(n)
    {
        post_order(n->left);
        post_order(n->right);
        cout<<n->data<<" ";
    }
}

void in_order(struct node* n)
{
    if(n)
    {
        in_order(n->left);
        in_order(n->right);
        cout<<n->data<<" ";
    }
}

bool search(struct node* root,int data)
{
    if(root==NULL)
    {
        return false;
    }
    else if(root->data==data)
    {
        return true;
    }
    else if(data<root->data)
    {
        return search(root->left,data);
    }
    else
    {
        return search(root->right,data);
    }
}

int main()
{
    struct node *root=NULL;

    while(1)
    {

    cout<<"\t------------------------"<<endl;
    cout<<"\t\tTREE"<<endl;
    cout<<"\t------------------------"<<endl;

    int n,a,b;
    cout<<"\t1.INSERT\n\t2.SEARCH\n\t3.PRE_ORDERPRINT\n\t4.POST_ORDERPRINT\n\t5.IN_ORDERPRINT\n\t6.EXIST\n\n"<<endl;
    cin>>n;

    switch(n)
    {
  case 1:
      cout<<"Enter data : ";
      cin>>a;
    root=insert(root,a);
    break;
  case 2:
      cout<<"Data to be searched : ";
    cin>>b;
    if(search(root,b)==true)
    {
        cout<<"Found\n"<<endl;
    }
    else
    {
        cout<<"Not found\n"<<endl;
    }
    break;

  case 3:
    pre_order(root);
    cout<<endl;
    break;
  case 4:
    post_order(root);
    cout<<endl;
    break;
  case 5:
    in_order(root);
    cout<<endl;
    break;
  case 6:
    return 0;


    }
    }
    return 0;
}

No comments:

Post a Comment