C program to create a binary search tree and for implementing the in order, Pre order, post order traversal using recursion
Source Code in C:
//program that will create a binary search tree and travese it in inorder, preoreder and postorder.
#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *right;
struct tnode *left;
};
struct tnode *CreateBST(struct tnode *, int);
void Inorder(struct tnode *);
void Preorder(struct tnode *);
void Postorder(struct tnode *);
int main()
{
struct tnode *root = NULL;
int choice, item, n, i;
do
{
printf("\n\n****Binary Search Tree Operations****");
printf("\n1. Creation of BST");
printf("\n2. Traverse in Inorder");
printf("\n3. Traverse in Preorder");
printf("\n4. Traverse in Postorder");
printf("\n5. Exit");
printf("\nEnter Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
root = NULL;
printf("\nBST for How Many Nodes ? ");
scanf("%d",&n);
for(i = 1; i <= n; i++)
{
printf("Enter data for node %d : ", i);
scanf("%d",&item);
root = CreateBST(root,item);
}
printf("\nBST with %d nodes is ready to Use!!", n);
break;
case 2:
printf("\nBST Traversal in INORDER:");
Inorder(root);
break;
case 3:
printf("\nBST Traversal in PREORDER:");
Preorder(root);
break;
case 4:
printf("\nBST Traversal in POSTORDER:");
Postorder(root);
break;
case 5:
printf("\nTerminating");
break;
default:
printf("\nInvalid Option !!! Try Again !!");
break;
}
} while(choice != 5);
return 0;
}
struct tnode* CreateBST(struct tnode *root, int item)
{
if(root == NULL)
{
root = (struct tnode *)malloc(sizeof(struct tnode));
root->left = root->right = NULL;
root->data = item;
return root;
}
else
{
if(item < root->data )
root->left = CreateBST(root->left,item);
else if(item > root->data )
root->right = CreateBST(root->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(root);
}
}
void Inorder(struct tnode *root)
{
if( root != NULL)
{
Inorder(root->left);
printf(" %d ",root->data);
Inorder(root->right);
}
}
void Preorder(struct tnode *root)
{
if( root != NULL)
{
printf(" %d ",root->data);
Preorder(root->left);
Preorder(root->right);
}
}
void Postorder(struct tnode *root)
{
if( root != NULL)
{
Postorder(root->left);
Postorder(root->right);
printf(" %d ",root->data);
}
}
Input/Output:
No comments:
Post a Comment