Monday, 11 December 2017

Write a C program that uses functions to perform the following:
a) Create a binary search tree of integers.
b) Traverse the above Binary search tree non recursively in inorder.

Implementation of above problem:
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef struct BST 
{
int data;
struct BST *leftChild;
struct BST*rightChild;
} node;
void insert(node *, node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int, node **);
/* Main function with different function call */
void main() 
{
int choice;
char ans = 'N';
int key;
node *newNode, *root, *temp, *parent;
node *getNode();
root = NULL;
clrscr();
while(1)
{
printf("\n ** Binary Search Tree MENU **");
printf("\n1. Create");
printf("\n2. Search");
printf("\n3. Display - Traversals");
printf("\n4. Exit");
printf("\n Please enter your choice :");
scanf("%d", &choice);
switch (choice) 
{
case 1:
do 
{
newNode = getNode();
printf("\n Please enter the Element to be insert: ");
scanf("%d", &newNode->data);
if (root == NULL) /* Tree is not Created */
root = newNode;
else
insert(root, newNode);
printf("\n Want to insert more Elements?(y/n)");
ans = getch();
while (ans == 'y');
break;
case 2:
printf("\n Enter Element to be search: ");
scanf("%d", &key);
temp = search(root, key, &parent);
printf("\n Parent of node %d is %d", temp->data, parent->data);
break;
case 3:
if (root == NULL)
printf("\n Tree Is Not Created");
else 
{
printf("\n The Inorder display : ");
inorder(root);
printf("\n The Preorder display : ");
preorder(root);
printf("\n The Postorder display : ");
postorder(root);
}
break;
case 4: exit(0);
default: printf("\n Please select correct operations!!!");
}
}
}
/* Creating a new Node for binary search tree*/
node *getNode() 
{
node *temp;
temp = (node *) malloc(sizeof(node));
temp->leftChild = NULL;
temp->rightChild = NULL;
return temp;
}
/* Inserting new Node into binary search tree */
void insert(node *root, node *newNode) 
{
if (newNode->data < root->data) 
{
if (root->leftChild == NULL)
root->leftChild = newNode;
else
insert(root->leftChild, newNode);
}
if (newNode->data > root->data) 
{
if (root->rightChild == NULL)
root->rightChild = newNode;
else
insert(root->rightChild, newNode);
}
}
/* Searching the node in binary Search Tree */
node *search(node *root, int key, node **parent) 
{
node *temp;
temp = root;
while (temp != NULL) 
{
if (temp->data == key) 
{
printf("\n The %d Element is Present", temp->data);
return temp;
}
*parent = temp;
if (temp->data > key)
temp = temp->leftChild;
else
temp = temp->rightChild;
}
return NULL;
}
/* Inorder traversal display */
void inorder(node *temp) 
{
if (temp != NULL) 
{
inorder(temp->leftChild);
printf("%d ", temp->data);
inorder(temp->rightChild);
}
}
/* Preorder traversal display */
void preorder(node *temp) 
{
if (temp != NULL) 
{
printf("%d ", temp->data);
preorder(temp->leftChild);
preorder(temp->rightChild);
}
}
/* Postorder traversal display */
void postorder(node *temp) 
{
if (temp != NULL) 
{
postorder(temp->leftChild);
postorder(temp->rightChild);
printf("%d ", temp->data);
}
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput