Thursday, 27 September 2012

Tree Using Opration Using C language

Tree

a tree is a widely used data structure that simulates a hierarchical tree structure with a set of linked nodes.
A tree can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of nodes (the "children"), with the constraints that no node is duplicated. A tree can be defined abstractly as a whole (globally) as an ordered tree

Menu based program for tree operation (Add,Delete,inorder,preorder,postorder print).

#include<stdio.h>
#include<conio.h>
/* Tree Implementation
   By Girfa
   Do not use it on any other website
   */
typedef struct st_tree
{
    struct st_tree *left;
    int data;
    struct st_tree *right;
}tree;
/* Function Prototype */
tree* create(int);
void insert(int n,tree **);
void inorder(tree *);
void preorder(tree *);
void postorder(tree*);
void del(int,tree **);
void main()
{
    tree *root=NULL;
    int n,s,opt;


    do
    {
        clrscr();
        printf("\n1. Add\n2. Inorder\n3. Preorder\n4. Postorder\n5. Delete\n0. Exit \nEnter your choice>> ");
        fflush(stdin);
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                printf("Enter number for add in tree>> ");
                scanf("%d",&n);
                insert(n,&root);
                break;

            case 2:
                inorder(root);
                getch();
                break;
            case 3:
                preorder(root);
                getch();
                break;
            case 4:
                postorder(root);
                getch();
                break;
            case 5:
                printf("Enter Number for delete>> ");
                scanf("%d",&n);
                del(n,&root);
                break;
            case 0:
                break;
            default:
                printf("\nInvalid Choice ");
                getch();
        }
    }while(opt!=0);
}
tree* create(int n)
{
    tree *nw;
    nw=(tree*) malloc(sizeof(tree));
    nw->data=n;
    nw->left=NULL;
    nw->right=NULL;
    return(nw);
}
//Function for insert a value into tree
void insert(int n,tree **rt)
{
    tree *nw,*pt,*pre;
    nw=create(n);
    if(*rt==NULL)
    {
        *rt=nw;
    }
    else
    {
        pt=*rt;
        while(pt!=NULL)
        {
            if(pt->data<n)
            {
                pre=pt;
                pt=pt->right;
            }
            else
            {
                pre=pt;
                pt=pt->left;
            }

        }
        if(n<pre->data)
            pre->left=nw;
        else
            pre->right=nw;
    }
}
void inorder(tree *rt)
{
    if(rt!=NULL)
    {
        inorder(rt->left);
        printf("[%d] ",rt->data);
        inorder(rt->right);
    }
}
void preorder(tree *rt)
{
    if(rt!=NULL)
    {
        printf("[%d] ",rt->data);
        preorder(rt->left);
        preorder(rt->right);
    }
}
void postorder(tree *rt)
{
    if(rt!=NULL)
    {
        postorder(rt->left);
        postorder(rt->right);
        printf("[%d] ",rt->data);
    }
}
/* function a number from tree */
void del(int n,tree **rt)
{
    tree *pt,*pre,*p;
    pt=*rt;
    /* Searching number */
    while(pt!=NULL)
    {
        if(pt->data==n)
            break;
        else
        {
            pre=pt;
            if(n<pt->data)
                pt=pt->left;
            else
                pt=pt->right;
        }
    }
    if(pt==NULL)
    {
        puts("Search number not found");
        getch();
    }
    else
    {
        /* Checking leaf node */
        if(pt->left==NULL && pt->right==NULL)
        {
            if(pt==*rt)
            {
                *rt=NULL;
            }
            else
            {
                if(pre->data<pt->data)
                    pre->right=NULL;
                else
                    pre->left=NULL;
            }
            free(pt);
        }
        else
        {
            /* Delete right child */
            if(pt->right!=NULL && pt->left==NULL)
            {
                if(pt==*rt)
                {
                    *rt=(*rt)->right;
                }
                else
                {
                    if(pre->data<pt->data)
                        pre->right=pt->right;
                    else
                        pre->left=pt->right;
                }
                free(pt);
            }
            else
            {
                /* Delete left child */
                if(pt->left!=NULL && pt->right==NULL)
                {
                    if(pt==*rt)
                        *rt=(*rt)->left;
                    else
                    {
                        if(pre->data<pt->data)
                            pre->right=pt->left;
                        else
                            pre->left=pt->left;
                    }

                }
                else
                {
                    /* Delete node which have both child left & Right */
                    if(pt==*rt)
                    {
                        p=pt->right;
                        while(p->left!=NULL)
                            p=p->left;
                        p->left=pt->left;
                        *rt=(*rt)->right;
                    }
                    else
                    {
                        p=pt->right;
                        while(p->left!=NULL)
                            p=p->left;
                        p->left=pt->left;
                        if(pre->data<pt->data)
                            pre->right=pt->right;
                        else
                            pre->left=pt->right;
                        free(pt);
                    }
                }
                free(pt);
            }

        }
    }
}