## 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

#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();
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)
{
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);
}

}
}
}