Posts
IMPLEMENTATION TREE TRAVERSAL
(INORDER – PREORDER – POST ORDER)
Exercise.No:6
NOTE:
* For any queries comment below, instantly the solution will be posted *
TO LEARN C PROGRAMMING FOLLOW THIS YOUTUBE CHANNEL: Code with u - YouTube
AIM:
To write the program to implement the Tree Traversal.
ALGORITHM:
1. Read the integers
2. Create the functions for preorder, in order and post order
3. Perform push and pop operations.
FOR INORDER
Inorder(pos t)
T!=null
Inorder(t-> left)
Printf(“%s”, t->data);
Inorder(t->right)
FOR PREORDER
Preorder(pos t)
T!=null
Printf(“%s”, t->data);
Preorder(t->left)
Inorder(t->right)
FOR POSTORDER
Postorder(pos t)
Postorder(t->left)
postorder(t->right)
Printf(“%s”, t->data);
4. Visit in the order left, root, right,
5. Display the visited nodes
PROGRAM:
// program showing various operations on Expression tree. Tree is created
// from a postfix expression
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef struct treenode
{
char 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;
}
treenode *create();
void inorder(treenode *T);
void preorder(treenode *T);
void postorder(treenode *T);
void main()
{
treenode *root=NULL,*p;
int x, op;
do
{
printf("\n\n1)Create\n2)Preorder");
printf("\n3)Inorder\n4)Postorder\n5)Quit");
printf("\n Enter 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;
}
}while(op<5);
}
void inorder(treenode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%c", T->data);
inorder(T->right);
}
}
void preorder(treenode *T)
{ if(T!=NULL)
{ printf("%c", T->data);
preorder(T->left);
preorder(T->right);
}
}
void postorder(treenode *T)
{ if(T!=NULL)
{
postorder(T->left);
postorder(T->right);
printf("%c", T->data);
}
}
treenode * create()
{
char a[50];
int i;
treenode *p,*q,*root;
stack s;
init(&s);
printf("\n Enter a postfix expression : ");
scanf("%s",&a);
for(i=0;a[i]!='\0';i++)
{
if(isalnum(a[i]))
{
p=(treenode*)malloc(sizeof(treenode));
p->left=p->right=NULL;
p->data=a[i];
push(&s,p);
}
else
{
q=pop(&s);
p=pop(&s);
root=(treenode*)malloc(sizeof(treenode));
root->left=p;
root->right=q;
root->data=a[i];
push(&s,root);
}
}
root=pop(&s);
return(root);
}
OUTPUT:
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :1
Enter a postfix expression: pk-ap+*
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :2
*-pk+ap
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :3
p-k*a+p
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :4
pk-ap+*
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :5
RESULT:
Thus, the program Tree Traversal was implemented and executed successfully.
IMPLEMENTATION OF BINARY SEARCH TREE AND ITS OPERATIONS
Exercise.No:7
NOTE:
* For any queries comment below, instantly the solution will be posted*
TO LEARN C PROGRAMMING FOLLOW THIS YOUTUBE CHANNEL: Code with u - YouTube
AIM:
To write the program to implement the Binary Search Tree and its operations.
ALGORITHM:
1. Read integers
2. Create binary tree with the functions insert, del, find min, display.
FOR INSERTION
If(T==null)
Newnode -> data=X;
Newnode->left=Null;
Newnode -> right=Null;
FOR DELETION
If(T== null)
Printf(“element not found”)
FINDMIN
If(T!=null)
If(t->left==null)
Return T;
DISPLAY
If(T!=null)
Display T->left;
Print f (“%d\t”, T->data);
Display(T->right);
4. Visit in the order left, root, right,
5. Display the visited nodes
PROGRAM:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct BSTnode
{
int data;
struct BSTnode *left,*right;
}BSTnode;
BSTnode *find(BSTnode *,int);
BSTnode *insert(BSTnode *,int);
BSTnode *delet(BSTnode *,int);
BSTnode *create();
void inorder(BSTnode *T);
void preorder(BSTnode *T);
void postorder(BSTnode *T);
void main()
{
BSTnode *root=NULL,*p;
int x, op;
do
{ printf("\n\n1)Create\n2)Delete\n3)Search\n4)Preorder");
printf("\n5)Inorder\n6)Postorder\n7)Insert\n8)Quit");
printf("\n Enter Your Choice :");
scanf("%d",&op);
switch(op)
{
case 1: root=create();
break;
case 2: printf("\n Enter the key to be deleted :");
scanf("%d",&x);
root=delet(root,x);
break;
case 3: printf("\n Enter the key to be searched :");
scanf("%d",&x);
p=find(root,x);
if(p==NULL)
printf("\n ***** Not Found****");
else
printf("\n ***** Found*****");
break;
case 4: preorder(root);
break;
case 5: inorder(root);
break;
case 6: postorder(root);
break;
case 7: printf("\n Enter a data to be inserted : ");
scanf("%d",&x);
root=insert(root,x);
break;
}
}while(op<8);
}
void inorder(BSTnode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d\t", T->data);
inorder(T->right);
}
}
void preorder(BSTnode *T)
{ if(T!=NULL)
{ printf("%d\t", T->data);
preorder(T->left);
preorder(T->right);
}
}
void postorder(BSTnode *T)
{ if(T!=NULL)
{
postorder(T->left);
postorder(T->right);
printf("%d\t", T->data);
}
}
BSTnode *find(BSTnode *root, int x)
{
while(root!=NULL)
{
if(x==root->data)
return(root);
if(x>root->data)
root=root->right;
else
root=root->left;
}
return(NULL);
}
BSTnode *insert(BSTnode *T, int x)
{
BSTnode *p,*q,*r;
r=(BSTnode*)malloc(sizeof(BSTnode));
r->data=x;
r->left=NULL;
r->right=NULL;
if(T==NULL)
return(r);
p=T;
while(p!=NULL)
{
q=p;
if(x>p->data)
p=p->right;
else
if(x<p->data)
p=p->left;
else
{
printf("\n Duplicate data : ");
return(T);
}
}
if(x>q->data)
q->right=r;
else
q->left=r;
return(T);
}
BSTnode *delet(BSTnode *T, int x)
{
BSTnode *temp;
if(T==NULL)
{
printf("\n Element not found :");
return(T);
}
if(x < T->data)
{
T->left=delet(T->left,x);
return(T);
}
if(x > T->data)
{
T->right=delet(T->right,x);
return(T);
}
if(T->left==NULL && T->right==NULL)
{
temp=T;
free(temp);
return(NULL);
}
if(T->left==NULL)
{
temp=T;
T=T->right;
free(temp);
return(T);
}
if(T->right==NULL)
{
temp=T;
T=T->left;
free(temp);
return(T);
}
temp=T->right;
while(temp->left !=NULL)
temp=temp->left;
T->data=temp->data;
T->right=delet(T->right, temp->data);
return(T);
}
BSTnode *create()
{
int n, x, i;
BSTnode *root;
root=NULL;
printf("\n Enter no. of nodes :");
scanf("%d",&n);
printf("\n Enter tree values :");
for(i=0;i<n; i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}
OUTPUT:
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :1
Enter no. of nodes :4
Enter tree values :5
6
7
3
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :3
Enter the key to be searched :4
***** Not Found****
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :4
5 3 6 7
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :5
3 5 6 7
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :6
3 7 6 5
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :7
Enter a data to be inserted: 32
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :4
5 3 6 7 32
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :2
Enter the key to be deleted :7
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :4
5 3 6 32
1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Postorder
7)Insert
8)Quit
Enter Your Choice :8
RESULT:
Thus, the program for Binary Search Tree operations was implemented and executed
successfully.
No comments:
Post a Comment