ASSIGNMENT 15 CS 392 : TCPTUTOR

0
33

PROBLEM STATEMENT

Write a C program to Construct a Binary Search Tree and traverse the tree in a)preorder, b)inorder and c)postorder.

ALGORITHM

Algorithm to insert a node Binary Search Tree (BST):
Step 1: Check whether root node is present or not (tree available or not). If root is NULL, create root node.
Step 2:  If the element to be inserted is less than the element present in the root node, traverse the left subtree recursively until we reach T→left/T→right is Null and place the new node at T→left (key in new node<key in t)/T→right(key in new node>key in T).
Step 3: If the element to be inserted is greater than the element present in root node, traverse the right subtree recursively until we reach T→left/T→right is NULL and place the new node at T→left/T→right.

Inorder Traversal
Step 1: Traverse the left subtree i.e., call in order(left subtree).
Step 2: Visit the root.
Step 3: Traverse the right subtree i.e., call inorder (right subtree).

Preorder Traversal
Step 1: Visit the root.
Step 2: Traverse the left subtree i.e., call preorder (left subtree).
Step 3: Traverse the right subtree i.e., call preorder(right subtree).

Postorder Traversal
Step 1: Traverse the left subtree i.e., call postorder(left subtree).
Step 2: Traverse the right subtree i.e., call postorder (right subtree).
Step 3: Visit the root.

SOURCE CODE

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *left,*right;
};
struct node *root;
struct node* create()
{
struct node *n;
n=(struct node*)malloc(sizeof(struct node));
n->left=NULL;
n->right=NULL;
return(n);
}
int insert(struct node* temp)
{
struct node *ptr,*pre;
printf(“Enter Your Data:”);
scanf(“%d”,&temp->info);
if(root==NULL)
root=temp;
else
{
pre=root;
while(pre!=NULL)
{
ptr=pre;
if(pre->info>temp->info)
{
pre=pre->left;
}
else if(pre->info<temp->info)
{
pre=pre->right;
}
}
if(ptr->info>temp->info)
ptr->left=temp;
else if(ptr->info<temp->info)
ptr->right=temp;
}
return(0);
}
int inorder(struct node* ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf(“%d,”,ptr->info);
inorder(ptr->right);
}
return(0);
}
int preorder(struct node* ptr)
{
if(ptr!=NULL)
{
printf(“%d,”,ptr->info);
preorder(ptr->left);
preorder(ptr->right);
}
return(0);
}
int postorder(struct node* ptr)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf(“%d,”,ptr->info);
}
return (0);
}
int main()
{
int ch;
struct node *temp,*ptr;
while(1)
{
printf(“\n1.Insert a node”);
printf(“\n2.Inorder Traversal”);
printf(“\n3.Preorder Traversal”);
printf(“\n4.Postorder Traversal”);
printf(“\n5.Exit\n”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
temp=create();
insert(temp);
break;
case 2:
ptr=root;
inorder(ptr);
break;
case 3:
ptr=root;
preorder(ptr);
break;
case 4:
ptr=root;
postorder(ptr);
break;
case 5:
exit(0);
default:
printf(“Enter Your Correct Choice:”);
}
}
return 0;
}

OUTPUT

1.Insert a node
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit
1
Enter Your Data:56
<MENU>
1
Enter Your Data:3
<MENU>
1
Enter Your Data:89
<MENU>
2
3,56,89,
<MENU>
3
56,3,89,
<MENU>
4
3,89,56,
<MENU>

*************************

SHARE
Previous articlememe test post
Next articleNOTIFICATIONS

LEAVE A REPLY

Please enter your comment!
Please enter your name here