Scribd
Upload
27 views16 pages

DS Lab Program10 (28-12-2020)

The document describes a C program that implements binary search tree operations including creating a BST from sample data, traversing the BST using inorder, preorder and postorder, searching for an element, and handling duplicate nodes. The program contains functions for inserting nodes, traversing the tree, and searching. It is modified to allow duplicate nodes by changing the comparison operator in the insert function from > to >=.

Uploaded by

rtf47507
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views16 pages

DS Lab Program10 (28-12-2020)

The document describes a C program that implements binary search tree operations including creating a BST from sample data, traversing the BST using inorder, preorder and postorder, searching for an element, and handling duplicate nodes. The program contains functions for inserting nodes, traversing the tree, and searching. It is modified to allow duplicate nodes by changing the comparison operator in the insert function from > to >=.

Uploaded by

rtf47507
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

Lab Program 10

/*Without Duplicate Node*/

Design, Develop and Implement a menu driven Program in C for the following
operations on Binary Search Tree (BST) of Integers.
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Postorder
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit
Program:

#include<stdio.h>
#include<stdlib.h>

struct node
{
int info;
struct node *lchild;
struct node *rchild;
};

typedef struct node *nodepointer;

nodepointer getnode()
{
nodepointer x;
x=(nodepointer)malloc(sizeof(struct node));
return x;
}
nodepointer insert(int item, nodepointer root)
{
nodepointer temp,cur,prev;
temp=getnode();
temp->info=item;
temp->lchild=temp->rchild=NULL;
if(root==NULL)
{
root=temp;
return root;
}
else
{
prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
if(temp->info < cur->info)
cur=cur->lchild;
else if(temp->info > cur->info)
cur=cur->rchild;
else
{
printf("Duplicate Node\n");
return root;
}
}
if(temp->info > prev->info)
prev->rchild=temp;
else
prev->lchild=temp;
return root;

}
}
void preorder(nodepointer root)
{
if(root!=NULL)
{
printf("%d\t",root->info);
preorder(root->lchild);
preorder(root->rchild);
}
}

void inorder(nodepointer root)


{
if(root!=NULL)
{
inorder(root->lchild);
printf("%d\t",root->info);
inorder(root->rchild);
}
}

void postorder(nodepointer root)


{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d\t",root->info);
}
}

void traversal(nodepointer root)


{
if(root==NULL)
{
printf("The tree is empty\n");
return;
}
printf("\nThe preorder traversal is\n");
preorder(root);
printf("\nThe inorder traversal is\n");
inorder(root);
printf("\nThe post order traversal is\n");
postorder(root);
}
void search(nodepointer root)
{
int key;
nodepointer cur;
printf("Enter the key element to be searched\n");
scanf("%d",&key);
if(root==NULL)
{
printf("The tree is empty\n");
return;
}
cur=root;
while(cur!=NULL)
{
if(key==cur->info)
{
printf("The key element %d is found in tree\n",key);
return;
}
if(key<cur->info)
cur=cur->lchild;
else
cur=cur->rchild;
}
printf("The key element %d is not found in the tree\n",key);
}
void main()
{
int ch,item;
nodepointer root=NULL;
clrscr();
while(1)
{
printf("\nBinary Search Tree Operations\n1.insert\t
2.traversal\t3.search\t4.exit\n");
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the item to be inserted\n");
scanf("%d",&item);
root=insert(item,root);
break;
case 2: traversal(root);
break;
case 3: search(root);
break;
case 4: exit(0);
default: printf("enter a valid choice\n");
}
}
}
Outputs:
/*With Duplicate Node*/
Program:
#include<stdio.h>
#include<stdlib.h>

struct node
{
int info;
struct node *lchild;
struct node *rchild;
};

typedef struct node *nodepointer;

nodepointer getnode()
{
nodepointer x;
x=(nodepointer)malloc(sizeof(struct node));
return x;
}
nodepointer insert(int item, nodepointer root)
{
nodepointer temp,cur,prev;
temp=getnode();
temp->info=item;
temp->lchild=temp->rchild=NULL;
if(root==NULL)
{
root=temp;
return root;
}
else
{
prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
if(temp->info < cur->info)
cur=cur->lchild;
else if(temp->info >= cur->info) /*Changes are shown in RED Colour*/
cur=cur->rchild;
}
if(temp->info >= prev->info) /*Changes are shown in RED Colour*/

prev->rchild=temp;
else
prev->lchild=temp;
return root;

}
}

void preorder(nodepointer root)


{
if(root!=NULL)
{
printf("%d\t",root->info);
preorder(root->lchild);
preorder(root->rchild);
}
}
void inorder(nodepointer root)
{
if(root!=NULL)
{
inorder(root->lchild);
printf("%d\t",root->info);
inorder(root->rchild);
}
}

void postorder(nodepointer root)


{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d\t",root->info);
}
}

void traversal(nodepointer root)


{
if(root==NULL)
{
printf("The tree is empty\n");
return;
}
printf("\nThe preorder traversal is\n");
preorder(root);
printf("\nThe inorder traversal is\n");
inorder(root);
printf("\nThe post order traversal is\n");
postorder(root);
}
void search(nodepointer root)
{
int key;
nodepointer cur;
printf("Enter the key element to be searched\n");
scanf("%d",&key);
if(root==NULL)
{
printf("The tree is empty\n");
return;
}
cur=root;
while(cur!=NULL)
{
if(key==cur->info)
{
printf("The key element %d is found in tree\n",key);
return;
}
if(key<cur->info)
cur=cur->lchild;
else
cur=cur->rchild;
}
printf("The key element %d is not found in the tree\n",key);
}
void main()
{
int ch,item;
nodepointer root=NULL;
clrscr();
while(1)
{
printf("\nBinary Search Tree Operations\n1.insert\t
2.traversal\t3.search\t4.exit\n");
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the item to be inserted\n");
scanf("%d",&item);
root=insert(item,root);
break;
case 2: traversal(root);
break;
case 3: search(root);
break;
case 4: exit(0);
default: printf("enter a valid choice\n");
}
}
}

You might also like