Tree:
Tree is a non-linear data structure consisting of data nodes connected
to each other with pointers, in such a same spirit as link list. A tree is an
abstract model of hierarchical structure that consists of nodes with a parent
child relation. Every tree started from node which is called root node. The
root node may be empty or may have children. Every other node has a parent node
and the node may have any numbers of children.
Algorithm to insert node in a tree
Step 1: If the current pointer node is null,
then create a new node and assign left and right part of node to null.
i.e. nn --> left = null
i.e. nn --> right = null
then insert the data to be inserted to
the newly created node and assign it as root node.
i.e. nn--> root
Step
2 : If the current pointer points to the root node (i.e. already contain the
root) then compare the node to be inserted with the root node.
If root > new node then place new node to the left side of root.
i.e. root --> left = new node
then assign left and right part
of node to null else
If root < new node then place
new node to the right side of root.
i.e root --> right = new node
then assign left and right part of new
node to null.
else if root = new node, then assign new
node as root node.
i.e. root = new node
else exit
Step
3 : Stop
Deletion of Binary Tree:
Case
I : Delete a leaf node.
Case
II : Delete a non-leaf having single children.
Case
III : Delete non-leaf having both children.
Program code of Tree Implemented in C programming
#include<stdio.h>
#include<math.h>
#include<malloc.h>
typedef struct tnode
{
int info;
struct tnode *l;
struct tnode *r;
}node;
node * root;
int create()
{
int n,i;
node *newn,*ptr,*pptr;
printf("Enter the no. of
node:\n");
scanf("%d",&n);
printf("enter %d value",n);
root=(node*)malloc(sizeof(node));
root->l=root->r=NULL;
scanf("%d",&root->info);
for(i=2;i<=n;i++)
{
newn=(node*)malloc(sizeof(node));
newn->l=newn->r='\0';
scanf("%d",&newn->info);
ptr=root;
while(ptr!='\0')
{
pptr=ptr;
if(newn->info<ptr->info)
{
ptr=ptr->l;
if(ptr=='\0')
{
pptr->l=newn;
}
}
else
{
ptr=ptr->r;
if(ptr==NULL)
{
pptr->r=newn;
}
}
}
}
}
void preorder(node *ptr)
{
if(ptr!='\0')
{
printf("%d ",ptr->info);
preorder(ptr->l);
preorder(ptr->r);
}
}
void inorder( node *ptr)
{
if(ptr!='\0')
{
inorder(ptr->l);
printf("%d ",ptr->info);
inorder(ptr->r);
}
}
void postorder(node *ptr)
{
if(ptr!='\0')
{
postorder(ptr->l);
postorder(ptr->r);
printf("%d ",ptr->info);
}
}
void main()
{
create();
printf("preorder:\n");
preorder(root);
printf("inorder:\n");
inorder(root);
printf("postorder:\n");
postorder(root);
}
No comments:
Post a Comment