#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct treenode
{
int data;
struct treenode *left,*right;
}treenode;
typedef struct stack
{ treenode *data[20];
int top;
}stack;
void init(stack *s)
{ s->top=-1;
}
treenode * pop(stack *s)
{ treenode *p;
p=s->data[s->top];
s->top=s->top-1;
return(p);
}
void push(stack *s, treenode *p)
{ s->top=s->top+1;
s->data[s->top]=p;
}
int empty(stack *s)
{ if(s->top==-1)
return(1);
return(0);
}
int full(stack *s)
{ if(s->top==19)
return(1);
return(0);
}
treenode *create();
void inorder(treenode *T);
void preorder(treenode *T);
void postorder(treenode *T);
void non_rec_preorder(treenode *T);
void non_rec_inorder(treenode *T);
void non_rec_postorder(treenode *T);
void main()
{
treenode *root=NULL,*p;
int x,op;
clrscr();
do
{ printf("\n\n1)Create\n2)Preorder(recursive)");
printf("\n3)Inorder(recursive)\n4)Posorder(Recursive)");
printf("\n5)Preorder(Non-Recursive)\n6)Inorder(Non-Recursive)");
printf("\n7)Postorder(Non-Recursive\n8)Quit");
printf("\nEnter Your Choice :");
scanf("%d",&op);
switch(op)
{
case 1:root=create();break;
case 2: preorder(root);break;
case 3: inorder(root);break;
case 4: postorder(root);break;
case 5: non_rec_preorder(root);break;
case 6: non_rec_inorder(root);break;
case 7: non_rec_postorder(root);break;
}
}while(op!=8);
}
void inorder(treenode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d ",T->data);
inorder(T->right);
}
}
void preorder(treenode *T)
{ if(T!=NULL)
{ printf("%d ",T->data);
preorder(T->left);
preorder(T->right);
}
}
void postorder(treenode *T)
{ if(T!=NULL)
{
postorder(T->left);
postorder(T->right);
printf("%d ",T->data);
}
}
void non_rec_preorder(treenode *T)
{ stack s;
init(&s);
printf("\n");
if(T==NULL)
return;
while(T!=NULL)
{ printf("%d ",T->data);
push(&s,T);
T=T->left;
}
while(!empty(&s))
{ T=pop(&s);
T=T->right;
while(T!=NULL)
{ printf("%d ",T->data);
push(&s,T);
T=T->left;
}
}
}
void non_rec_inorder(treenode *T)
{ stack s;
init(&s);
printf("\n");
if(T==NULL)
return;
while(T!=NULL)
{ push(&s,T);
T=T->left;
}
while(!empty(&s))
{ T=pop(&s);
printf("%d ",T->data);
T=T->right;
while(T!=NULL)
{ push(&s,T);
T=T->left;
}
}
}
void non_rec_postorder(treenode *T)
{ stack s,s1;
treenode *flag;
init(&s);init(&s1);
printf("\n");
if(T==NULL)
return;
while(T!=NULL)
{ push(&s,T);push(&s1,NULL);
T=T->left;
}
while(!empty(&s))
{ T=pop(&s);flag=pop(&s1);
if(flag!=NULL)
printf("%d ",T->data);
else
{push(&s,T);push(&s1,(treenode*)1);
T=T->right;
while(T!=NULL)
{ push(&s,T);push(&s1,NULL);
T=T->left;
}
}
}
}
treenode *create()
{ treenode *root,*b[31];
int x,i;
//For creation of a tree, tree is mapped to an array
for(i=1;i<30;i++)
b[i]=NULL;
/*left child of ith node will be at 2*i and right child at 2*i+1*/
printf("\nPlease Enter data of root node(-1 for does not exist): ");
scanf("%d",&x);
if(x==-1)
return(root);
b[1]=(treenode*)malloc(sizeof(treenode));
b[1]->data=x;
b[1]->left=b[1]->right=NULL;
for(i=1;i<=15;i++)
if(b[i]!=NULL)
{ printf("\nEnter Left child of %d (-1 for does not exist): ",b[i]->data);
scanf("%d",&x);
if(x!=-1)
{
b[2*i]=(treenode*)malloc(sizeof(treenode));
b[2*i]->data=x;
b[2*i]->left=NULL;
b[2*i]->right=NULL;
b[i]->left=b[2*i];
}
printf("\nEnter right child of %d (-1 for does not exist) : ",b[i]->data);
scanf("%d",&x);
if(x!=-1)
{b[2*i+1]=(treenode*)malloc(sizeof(treenode));
b[2*i+1]->data=x;
b[2*i+1]->left=NULL;
b[2*i+1]->right=NULL;
b[i]->right=b[2*i+1];
}
}
return(b[1]);
}
OUTPUT:-
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :1
Please Enter data of root node(-1 for does not exist): 45
Enter Left child of 45 (-1 for does not exist): 23
Enter right child of 45 (-1 for does not exist) : 47
Enter Left child of 23 (-1 for does not exist): -1
Enter right child of 23 (-1 for does not exist) : -1
Enter Left child of 47 (-1 for does not exist): 56
Enter right child of 47 (-1 for does not exist) : -1
Enter Left child of 56 (-1 for does not exist): 90
Enter right child of 56 (-1 for does not exist) : 33
Enter Left child of 90 (-1 for does not exist): -1
Enter right child of 90 (-1 for does not exist) : -1
Enter Left child of 33 (-1 for does not exist): -1
Enter right child of 33 (-1 for does not exist) : -1
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :2
45 23 47 56 90 33
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :3
23 45 90 56 33 47
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :4
23 90 33 56 47 45
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :5
45 23 47 56 90 33
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :6
23 45 90 56 33 47
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :7
23 90 33 56 47 45
1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :8
The complete blogs are really inconceivable and definitely everyone will share this information.
ReplyDeletec++ programming tutorial