Home >> Sem 2 >> Programming Skills II(DS)
GUJARAT TECHNOLOGICAL UNIVERSITY
Subject Name : Programming Skills II(DS)
Subject Code : 620002
GUJARAT TECHNOLOGICAL UNIVERSITY
Subject Name : Programming Skills II(DS)
Subject Code : 620002
Last Update : 03/June/2010
13. Write a program to implement sparse Matrix ( using Array & Linked-List) //To Implement Sparse Matrix(Using Array & Linked-List)
#include<stdio.h>
struct Matrix
{
int row,col,elem;
struct Matrix *next;
}*start=NULL,*link=NULL,*temp=NULL;
void insert(int n,int r,int c)
{
temp=(struct Matrix *) malloc(sizeof(struct Matrix));
if(temp==NULL)
printf("\nNo sufficient Memory !!!");
else
{
temp->row=r;
temp->col=c;
temp->elem=n;
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
link->next=temp;
}
}
}
void createLL(int a[][5])
{
int i,j;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
if(a[i][j]!=0)
{
insert(a[i][j],i,j);
}
}
}
}
void showLL()
{
int i,j;
if(start==NULL)
return;
else
{
printf("The Matrix is:\n");
link=start;
while(link!=NULL)
{
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
if(link->row==i && link->col==j)
{
printf("\t%d",link->elem);
link=link->next;
}
else
printf("\t0");
}
printf("\n");
}
}
}
}
void main()
{
int a[5][5],i,j,cnt=0;
clrscr();
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
printf("Enter Element M[%d][%d] ",i,j);
scanf("%d",&a[i][j]);
if(a[i][j]!=0)
cnt++;
}
}
clrscr();
createLL(a);
showLL();
getch();
}
14. (a) Write a program to create a sorted doubly linked list....
//(a) Write a program to create a sorted doubly linked list.
//Sorted Doubly Linked-List
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void create()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp==NULL)
printf("\nNo sufficient Memory !!!");
else
{
printf("Enter No.: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else if(start->no > temp->no)
{
temp->next=start;
start->prev=temp;
start=temp;
}
else
{
link=start;
while(link->next!=NULL)
{
if(link->no <= temp->no)
link=link->next;
else
break;
}
if(link->next==NULL && link->no <= temp->no)
{
link->next=temp;
temp->prev=link;
}
else
{
temp->prev=link->prev;
temp->next=link;
link->prev->next=temp;
link->prev=temp;
}
}
}
}
void trav()
{
link=start;
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
void main()
{
int ch;
do
{
do
{
clrscr();
printf("Do You want to Insert Node?\n1. YES\n2. NO\n");
scanf("%d",&ch);
}while(ch<1 || ch>2);
if(ch==1)
create();
else if(start==NULL)
printf("\nLinked-List is Empty");
else
{
clrscr();
printf("\nThe Linked-List is:\n");
trav();
}
}while(ch==1);
getch();
}
//(b) Write a program to create a doubly linked list in LIFO fashion.
//Doubly Linked-List in LIFO fashion.
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void insert()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo sufficient Memory");
else
{
printf("Enter Value: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(start == NULL)
start=temp;
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
}
printf("\nNode is Inserted at Last");
}
}
void delet()
{
if(start==NULL)
printf("\nList is Empty");
else if(start->next==NULL)
{
printf("\nThe Deleted Item is:");
printf("\n %d",start->no);
free(start);
start=NULL;
}
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
printf("\nThe Deleted Item is:");
printf("\n %d",link->no);
temp=link;
link=link->prev;
link->next=NULL;
free(temp);
}
}
void view()
{
if(start==NULL)
printf("\nList is Empty");
else
{
printf("\nThe List is:");
link=start;
while(link!=NULL)
{
printf("\n %d",link->no);
link=link->next;
}
}
}
void main()
{
int ch,value,i;
clrscr();
do
{
do
{
clrscr();
printf("\n1. Insert\n2. Delete \n3. View\n4. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>4);
switch(ch)
{
case 1:
insert();
getch();
break;
case 2:
delet();
getch();
break;
case 3:
view();
getch();
}
}while(ch!=4);
}
//(c) Write a program to create a doubly linked list in FIFO fashion.
//Doubly Linked-List in FIFO fashion.
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void insert()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo sufficient Memory");
else
{
printf("Enter Value: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(start == NULL)
start=temp;
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
}
printf("\nNode is Inserted at Last");
}
}
void delet()
{
if(start==NULL)
printf("\nList is Empty");
else if(start->next==NULL)
{
printf("\nThe Deleted Item is:");
printf("\n %d",start->no);
free(start);
start=NULL;
}
else
{
temp=start;
start=start->next;
start->prev=NULL;
printf("\nThe Deleted Item is:");
printf("\n %d",temp->no);
free(temp);
}
}
void view()
{
if(start==NULL)
printf("\nList is Empty");
else
{
printf("\nThe List is:");
link=start;
while(link!=NULL)
{
printf("\n %d",link->no);
link=link->next;
}
}
}
void main()
{
int ch,value,i;
clrscr();
do
{
do
{
clrscr();
printf("\n1. Insert\n2. Delete \n3. View\n4. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>4);
switch(ch)
{
case 1:
insert();
getch();
break;
case 2:
delet();
getch();
break;
case 3:
view();
getch();
}
}while(ch!=4);
}
//(d) Write a program perform the following operations on a doubly linkedList.
//Perform some Operations on Doubly Linked-List
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void insert()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter ID: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(start==NULL)
start=temp;
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
}
printf("\nNode is Inserted at Last");
}
}
void delet()
{
if(start==NULL)
printf("\nLinked-List is Empty");
else if(start->next==NULL)
{
printf("\nThe Deleted Item is:");
printf("\n %d",start->no);
free(start);
start=NULL;
}
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
printf("\nThe Deleted Item is:");
printf("\n %d",link->no);
temp=link;
link=link->prev;
link->next=NULL;
free(temp);
}
}
void sum()
{
if(start==NULL)
printf("\nLinked-List is Empty");
else
{
int s=0;
link=start;
while(link!=NULL)
{
s=s+link->no;
link=link->next;
}
printf("\nSum of Elements of the List is %d",s);
}
}
void count_node()
{
int n=0;
link=start;
while(link!=NULL)
{
n++;
link=link->next;
}
printf("\nTotal no. of nodes in the List are %d",n);
}
void search(int val)
{
if(start==NULL)
printf("\nLinked-List is Empty");
else
{
link=start;
while(link!=NULL)
{
if(link->no==val)
{
printf("\nThe Number is Exist in the List");
break;
}
link=link->next;
}
if(link==NULL)
printf("\nThe Number is not Exist in the List");
}
}
void reverse_LL()
{
struct List *fst=NULL;
if(start==NULL)
{
printf("\nLinked-List is Empty");
return;
}
else if(start->next!=NULL)
{
fst=link=start;
start=NULL;
while(link!=NULL)
{
while(link->next!=NULL)
{
link=link->next;
}
if(start==NULL)
{
start=link;
link=link->prev;
start->prev=NULL;
link->next=NULL;
}
else
{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=link;
link=link->prev;
temp->next->prev=temp;
link->next=NULL;
}
if(link==fst)
fst=NULL;
else
link=fst;
}
}
printf("\nLinked-List is Reversed");
link=start;
printf("\nLinked-List: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
void copy_LL()
{
struct List *first=NULL,*trav=NULL;
if(start==NULL)
printf("\nLinked-List is Empty");
else
{
link=start;
while(link!=NULL)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
{ printf("\nNo Sufficient Memory!!!");
break;
}
else
{
temp->no=link->no;
temp->prev=temp->next=NULL;
if(first==NULL)
first=temp;
else
{
trav=first;
while(trav->next!=NULL)
{
trav=trav->next;
}
temp->prev=trav;
trav->next=temp;
}
}
link=link->next;
}
printf("\nLinked-List is copied");
trav=first;
while(trav!=NULL)
{
printf("\n%d",trav->no);
temp=trav;
trav=trav->next;
free(temp);
}
}
}
void traverse()
{
if(start==NULL)
printf("\nLinked-List is Empty");
else
{
link=start;
printf("\nLinked-List: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
}
void main()
{
int ch,v;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. Delete\n3. Sum of elements of the List");
printf("\n4. No. of Nodes\n5. Searching\n");
printf("6. Reverse the List\n7. Copy the List");
printf("\n8. Traversal\n9. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>9);
switch(ch)
{ case 1:
insert();
getch();
break;
case 2:
delet();
getch();
break;
case 3:
sum();
getch();
break;
case 4:
count_node();
getch();
break;
case 5:
printf("Enter the Value: ");
scanf("%d",&v);
search(v);
getch();
break;
case 6:
reverse_LL();
getch();
break;
case 7:
copy_LL();
getch();
break;
case 8:
traverse();
getch();
}
}while(ch!=9);
}
//---------AND---------------MoRe--------
//Perform concate, Union and Intersection Operations on Two Doubly Linked-List
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*L1start=NULL,*L2start=NULL,*link=NULL,*temp=NULL;
void insert(int l)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter ID: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(l==1)
{
if(L1start==NULL)
L1start=temp;
else
{
link=L1start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
printf("\nNode is Inserted at Last in List1");
}
}
else
{
if(L2start==NULL)
L2start=temp;
else
{
link=L2start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
printf("\nNode is Inserted at Last in List2");
}
}
}
}
void delet(int l)
{
if(l==1)
{
if(L1start==NULL)
printf("\nLinked-List1 is Empty");
else if(L1start->next==NULL)
{
printf("\nThe Deleted Item is:");
printf("\n %d",L1start->no);
free(L1start);
L1start=NULL;
}
else
{
link=L1start;
while(link->next!=NULL)
{
link=link->next;
}
printf("\nThe Deleted Item is:");
printf("\n %d",link->no);
temp=link;
link=link->prev;
link->next=NULL;
free(temp);
}
}
else
{
if(L2start==NULL)
printf("\nLinked-List2 is Empty");
else if(L2start->next==NULL)
{
printf("\nThe Deleted Item is:");
printf("\n %d",L2start->no);
free(L2start);
L2start=NULL;
}
else
{
link=L2start;
while(link->next!=NULL)
{
link=link->next;
}
printf("\nThe Deleted Item is:");
printf("\n %d",link->no);
temp=link;
link=link->prev;
link->next=NULL;
free(temp);
}
}
}
void traverse()
{
if(L1start==NULL)
printf("\nLinked-List1 is Empty");
else
{
link=L1start;
printf("\nLinked-List1: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
if(L2start==NULL)
printf("\nLinked-List2 is Empty");
else
{
link=L2start;
printf("\nLinked-List2: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
}
void concate(int t)
{
struct List *trav=NULL;
if(t==1)
{
link=L2start;
while(link!=NULL)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
temp->no=link->no;
temp->prev=temp->next=NULL;
if(L1start==NULL)
L1start=temp;
else
{
trav=L1start;
while(trav->next!=NULL)
trav=trav->next;
temp->prev=trav;
trav->next=temp;
}
}
link=link->next;
}
}
else
{
link=L1start;
while(link!=NULL)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
temp->no=link->no;
temp->next=NULL;
if(L2start==NULL)
L2start=temp;
else
{
trav=L2start;
while(trav->next!=NULL)
trav=trav->next;
temp->prev=trav;
trav->next=temp;
}
}
link=link->next;
}
}
traverse();
}
void Union()
{
struct List *unionfst=NULL,*trav=NULL;
if(L1start!=NULL)
{
link=L1start;
while(link!=NULL)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
temp->no=link->no;
temp->prev=temp->next=NULL;
if(unionfst==NULL)
unionfst=temp;
else
{
trav=unionfst;
while(trav->next!=NULL)
{
if(trav->no!=temp->no)
trav=trav->next;
else
break;
}
if(trav->next==NULL && trav->no!=temp->no)
{
temp->prev=trav;
trav->next=temp;
}
}
}
link=link->next;
}
}
if(L2start!=NULL)
{
link=L2start;
while(link!=NULL)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
temp->no=link->no;
temp->prev=temp->next=NULL;
if(unionfst==NULL)
unionfst=temp;
else
{
trav=unionfst;
while(trav->next!=NULL)
{
if(trav->no!=temp->no)
trav=trav->next;
else
break;
}
if(trav->next==NULL && trav->no!=temp->no)
{
temp->prev=trav;
trav->next=temp;
}
}
}
link=link->next;
}
}
if(unionfst==NULL)
printf("\nUnion of Both Linked-List is Empty");
else
{
link=unionfst;
printf("\nUnion of Both Linked-List: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
}
void intersect()
{
struct List *interfst=NULL,*trav1=NULL,*trav2=NULL;
if(L1start!=NULL && L2start!=NULL)
{
link=L1start;
while(link!=NULL)
{
trav1=L2start;
while(trav1!=NULL)
{
if(link->no==trav1->no)
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
temp->no=link->no;
temp->prev=temp->next=NULL;
if(interfst==NULL)
interfst=temp;
else
{
trav2=interfst;
while(trav2->next!=NULL)
{
if(trav2->no!=temp->no)
trav2=trav2->next;
else
break;
}
if(trav2->next==NULL && trav2->no!=temp->no)
{
temp->prev=trav2;
trav2->next=temp;
}
}
}
break;
}
else
trav1=trav1->next;
}
link=link->next;
}
}
if(interfst==NULL)
printf("\nIntersection of Both Linked-List is Empty");
else
{
link=interfst;
printf("\nIntersection of Both Linked-List: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
}
int choice()
{
int L;
do
{
printf("You want perform the operation on\n");
printf("1. List1\n2. List2\nEnter Your Chice: ");
scanf("%d",&L);
}while(L<1 || L>2);
return L;
}
void main()
{
int ch,v,t;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. Delete\n3. Concatenation\n4. Union");
printf("\n5. Intersection\n6. Traversal\n7. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>7);
switch(ch)
{ case 1:
insert(choice());
getch();
break;
case 2:
delet(choice());
getch();
break;
case 3:
do
{
printf("Concate\n");
printf("1. List1 before List2\n2. List2 before List1");
printf("\nEnter Your Chice: ");
scanf("%d",&t);
}while(t<1 || t>2);
concate(t);
getch();
break;
case 4:
Union();
getch();
break;
case 5:
intersect();
getch();
break;
case 6:
traverse();
getch();
break;
}
}while(ch!=7);
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
15.Write a program to swap two adjacent nodes by pointers (and not the data) of..
//Swap two adjacent nodes by pointers(and not the data) of Singly linked list
#include<stdio.h>
struct List
{
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void create()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp==NULL)
printf("\nNo sufficient Memory !!!");
else
{
printf("Enter No.: ");
scanf("%d",&temp->no);
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
link->next=temp;
}
}
}
void swap()
{
struct List *add=NULL;
if(start->next!=NULL)
{
link=start;
start=start->next;
while(link->next!=NULL)
{
if(link->next->next->next!=NULL)
{
temp=link->next->next;
add=link->next->next->next;
link->next->next=link;
link->next=add;
link=temp;
}
else if(link->next->next!=NULL)
{
add=link->next->next;
link->next->next=link;
link->next=add;
link=link->next;
}
else
{
link->next->next=link;
link->next=NULL;
}
}
}
printf("\n\nNodes are Swapped");
}
void show()
{
link=start;
printf("\nLinked-List is: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
void main()
{
int n;
do
{
clrscr();
printf("How many nodes you want to create?");
scanf("%d",&n);
}while(n<=0);
for(;n>0;n--)
{
create();
}
clrscr();
printf("Nodes are created");
show();
swap();
show();
getch();
}
//----------------------------------
//Swap two adjacent nodes by pointers(and not the data) of Doubly linked list
#include<stdio.h>
struct List
{
struct List *prev;
int no;
struct List *next;
}*start=NULL,*link=NULL,*temp=NULL;
void create()
{
temp=(struct List *) malloc(sizeof(struct List));
if(temp==NULL)
printf("\nNo sufficient Memory !!!");
else
{
printf("Enter No.: ");
scanf("%d",&temp->no);
temp->prev=temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
link=start;
while(link->next!=NULL)
{
link=link->next;
}
temp->prev=link;
link->next=temp;
}
}
}
void swap()
{
if(start->next!=NULL)
{
link=start;
start=start->next;
while(link!=NULL)
{
if(link->next==NULL)
{
link->prev=link->prev->next;
link=NULL;
}
else if(link->next->next==NULL)
{
if(link->next==start)
{
link->next->next=link;
link->next->prev=NULL;
link->prev=link->next;
link->next=NULL;
link=NULL;
}
else
{
link->next->next=link;
link->next->prev=link->prev->next;
link->prev=link->next;
link->next=NULL;
link=NULL;
}
}
else
{
if(link->next==start)
{
temp=link->next->next;
link->next->next=link;
link->next->prev=NULL;
link->prev=link->next;
if(temp->next!=NULL)
link->next=temp->next;
else
link->next=temp;
link=temp;
}
else
{
temp=link->next->next;
link->next->next=link;
link->next->prev=link->prev->next;
link->prev=link->next;
if(temp->next!=NULL)
link->next=temp->next;
else
link->next=temp;
link=temp;
}
}
}
}
printf("\n\nNodes are Swapped");
}
void show()
{
link=start;
printf("\nLinked-List is: ");
while(link!=NULL)
{
printf(" %d",link->no);
link=link->next;
}
}
void main()
{
int n;
do
{
clrscr();
printf("How many nodes you want to create?");
scanf("%d",&n);
}while(n<=0);
for(;n>0;n--)
{
create();
}
clrscr();
printf("Nodes are created");
show();
swap(n);
show();
getch();
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
***THREE IN ONE (16,17,18)
Shared By :Sonam Patel(SRIMCA college-Tarsadi)Show/Hide Program
//Create a Binary Tree
//And Print it's elements in PreOrder, InOrder and PostOrder (iterative code).
//Also Print it's elements using Breadth-First Travarsal.
#include<stdio.h>
struct Btree
{
struct Btree *Lsubtree;
int no;
struct Btree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
struct Btree *q[25];
int first=-1,last=-1;
int CQEmpty()
{
if(first == -1 && last == -1)
return 1;
else
return 0;
}
void CQins(struct Btree *addr)
{
if(first == -1)
first = last = 0;
else if(last == 24)
last=0;
else
last = last + 1;
q[last]=addr;
}
struct Btree * CQdel()
{
struct Btree *t;
t=q[first];
if(first == last)
first=last=-1;
else if(first == 24)
first=0;
else
first = first + 1;
return t;
}
void Treeins()
{
temp=(struct Btree *) malloc(sizeof(struct Btree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
root=temp;
else
{
link=root;
while(link != NULL)
{
if(link->Lsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(link->Lsubtree);
else
{
printf("Queue is Full");
return;
}
}
else
{
link->Lsubtree = temp;
break;
}
if(link->Rsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(link->Rsubtree);
else
{
printf("Queue is Full");
return;
}
}
else
{
link->Rsubtree = temp;
break;
}
if(CQEmpty() == 0)
link=CQdel();
}
}
printf("\nNode is Inserted");
}
}
void Preorder(struct Btree *rt)
{
if(rt != NULL)
{
printf(" %d",rt->no);
Preorder(rt->Lsubtree);
Preorder(rt->Rsubtree);
}
else
return;
}
void Inorder(struct Btree *rt)
{
if(rt != NULL)
{
Inorder(rt->Lsubtree);
printf(" %d",rt->no);
Inorder(rt->Rsubtree);
}
else
return;
}
void Postorder(struct Btree *rt)
{
if(rt != NULL)
{
Postorder(rt->Lsubtree);
Postorder(rt->Rsubtree);
printf(" %d",rt->no);
}
else
return;
}
void Breadth_First(struct Btree *pnt)
{
while(pnt != NULL)
{
printf(" %d",pnt->no);
if(pnt->Lsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Lsubtree);
else
{
printf("Queue is Full");
return;
}
}
if(pnt->Rsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Rsubtree);
else
{
printf("Queue is Full");
return;
}
}
if(CQEmpty() == 0)
pnt=CQdel();
else
pnt=NULL;
}
return;
}
void main()
{
int ch;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
printf("\nPreOrder: ");
Preorder(root);
printf("\nInOrder: ");
Inorder(root);
printf("\nPostOrder: ");
Postorder(root);
first = last = -1;
printf("\nBreadth-First: ");
Breadth_First(root);
getch();
}
}while(ch!=3);
}
16. Write a program to create a binary search tree and print it’s elements in inorder ..
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi)Show/Hide Program
/*Create a Binary Search Tree and print it's elements in Inorder.*/
#include<stdio.h>
#include<conio.h>
struct BinTree
{
struct BinTree *left;
int no;
struct BinTree *right;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BinTree *) malloc(sizeof(struct BinTree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->left != NULL && link->no > temp->no)
link=link->left;
if(link->left == NULL && link->no > temp->no)
{
link->left = temp;
printf("\nNode is Inserted");
return;
}
while(link->right != NULL && link->no < temp->no)
link=link->right;
if(link->right == NULL && link->no < temp->no)
{
link->right = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Inorder(struct BinTree *node)
{
if(node != NULL)
{
Inorder(node->left);
printf(" %d",node->no);
Inorder(node->right);
}
else
return;
}
void main()
{
int ch;
do
{
clrscr();
printf("\n1. Insert\n2. InOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
Treeins();
getch();
break;
case 2:
printf("\nInOrder: ");
Inorder(root);
getch();
case 3: exit();
default: printf("You have entered wrong choice\n");
}
}while(ch!=3);
}
Shared By :Neelam Patel(SRIMCA college-Tarsadi)Show/Hide Program
//inorder traversal using stack
#include<stdio.h>
#include<conio.h>
#define ALLOCATE (struct btree *)malloc(sizeof(struct btree))
struct btree
{
int no;
struct btree *left,*right;
}*root=NULL ;
typedef struct btree node;
void create(node *root,node *newnode)
{
if(newnode->no < root->no)
{
if(root->left==NULL)
root->left=newnode;
else
create(root->left,newnode);
}
if(newnode->no > root->no)
{
if(root->right==NULL)
root->right=newnode;
else
create(root->right,newnode);
}
}
void get_data(int n)
{
node *temp;
temp=ALLOCATE;
temp->left=NULL;
temp->right=NULL;
temp->no=n;
if(root==NULL)
root=temp;
else
create(root,temp);
}
void preorder(int n)
{
int top=1;
int *stack=(int *)malloc(n*2);
node *temp;
temp=root;
stack[1]=NULL;
if(temp==NULL)
printf("Tree is not created !! ");
else
{
while( temp != NULL)
{
printf("-> %d ",temp->no);
if (temp->right != NULL)
{
top=top+1; // push into stack
stack[top]=temp->right;
}
if (temp->left != NULL)
temp=temp->left;
else
{
temp=stack[top];
top=top-1; //pop from stack
}
}
}
}
void main()
{
int ch,i,n,val;
i=1;
do
{
clrscr();
printf("\n MAIN MENU ");
printf("\n-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*");
printf("\n1.CREATE\n2.PREOREDR TRAVERSAL \n3.EXIT ");
printf("\n-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*");
printf("\n\nENTER YOUR CHOICE:-");
scanf("%d",&ch);
switch(ch)
{
case 1 : printf("Enter the root of tree := ");
scanf("%d",&n);
printf("\n Enter data (For stop Enter 99 ) :\n");
get_data(n);
while(1)
{
printf("Enter Number :- ");
scanf("%d",&val);
if(val== 99)
break;
else
{
get_data(val);
i++;
}
}
break;
case 2 : printf("\n Inorder Traversal");
printf("\n----------------------------------");
printf("\nElements in the tree are .... ...\n");
preorder(i);
break;
case 3 : printf("\n\n EXITING ..... !! ");
break;
default : printf("Invalid Option !! ");
}
getch();
}while(ch!=3);
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi)Show/Hide Program
//Create a Binary Search Tree
//And print it's elements in Inorder (iterative code).
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Inorder(struct BStree *rt)
{
if(rt != NULL)
{
Inorder(rt->Lsubtree);
printf(" %d",rt->no);
Inorder(rt->Rsubtree);
}
else
return;
}
void main()
{
int ch;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. InOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
printf("\nInOrder: ");
Inorder(root);
getch();
}
}while(ch!=3);
}
Shared By :Hiren Patel(SRIMCA college-Tarsadi)Show/Hide Program
#include<stdio.h>
#include<conio.h>
struct bstree
{
struct bstree *left;
int val;
struct bstree *right;
}*temp=NULL,*link=NULL,*root=NULL;
void insertpos()
{
if(link==NULL)
{
root=temp;
link=root;
}
else
{
if(temp->val > link->val)
{
if(link->right!=NULL)
{
link=link->right;
insertpos();
}
else
link->right=temp;
}
else if(temp->val < link->val)
{
if(link->left!=NULL)
{
link=link->left;
insertpos();
}
else
link->left=temp;
}
else
{
printf("\nYOU CAN'T ENTER SAME DATA\n");
}
}
}
void insertnode()
{
temp=(struct bstree *)malloc(sizeof(struct bstree));
printf("Enter a Value : ");
scanf("%d",&temp->val);
link=root;
insertpos();
temp->left=NULL;
temp->right=NULL;
}
void inorder(struct bstree * root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->val);
inorder(root->right);
}
}
void main()
{
int ch;
clrscr();
do{
clrscr();
printf("1. Insert\n2. Display Node\n3. Exit\nEnter your choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertnode();
printf("\nInserted Successfully...");
getch();
break;
case 2:
printf("\n-----: INORDER :-----\n");
inorder(root);
getch();
break;
case 3:
break;
default :
printf("\nYou have enter wrong choice");
getch();
}
}while(ch!=3);
}
17. Write a program to create a binary search tree and print it’s elements in preorder..
Shared By :Jimeet Shah(C.U.Shah College Of MCA Wadhwan) Show/Hide Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct tree
{
struct tree *lptr;
int info;
struct tree *rptr;
}*root;
void insert(int);
void del(struct tree *);
void preorder(struct tree *);
void main()
{
int choice;
while(1)
{
printf("\n1.Create Tree\Insert Data Into Tree");
printf("\n2.Delete Node");
printf("\n3.View In Preorder");
printf("\n4.Exit");
printf("\nEnter Choice:-");
scanf("%d",&choice);
int no;
switch(choice)
{
case 1:
printf("Enter No:-");
scanf("%d",&no);
insert(no);
break;
case 2:
del(root);
break;
case 3:
preorder(root);
break;
case 4:
exit(0);
default:
printf("Invalid Choice");
break;
}
}
}
void insert(int num)
{
struct tree *temp,*new1;
new1=(struct tree *)malloc(sizeof(struct tree));
new1->info=num;
new1->lptr=NULL;
new1->rptr=NULL;
if(root==NULL)
{
root=new1;
}
else
{
temp=root;
while((num<temp->info && temp->lptr!=NULL) || (num>temp->info && temp->rptr!=NULL))
{
if(num<temp->info)
{
temp=temp->lptr;
}
else
{
temp=temp->rptr;
}
}
if(num<temp->info)
{
temp->lptr=new1;
}
else
{
temp->rptr=new1;
}
}
}
void del(struct tree *cur)
{
int dno,bool=0;
char d;
struct tree *temp,*q,*suc,*pred;
if(cur==NULL)
{
printf("No elements to delete");
exit(1);
}
printf("\nEnter No. to be deleted:-");
scanf("%d",&dno);
while(cur!=NULL && bool==0)
{
if(cur->info==dno)
{
bool=1;
}
else
{
if(dno<cur->info)
{
temp=cur;
cur=cur->lptr;
d='L';
}
else
{
temp=cur;
cur=cur->rptr;
d='R';
}
}
}
if(bool==0)
{
printf("\nNo Node Found");
exit(1);
}
if(cur->lptr==NULL)
{
q=cur->rptr;
}
else if(cur->rptr==NULL)
{
q=cur->lptr;
}
else
{
suc=cur->rptr;
if(suc->lptr==NULL)
{
suc->lptr=cur->lptr;
q=suc;
}
else
{
pred=cur->rptr;
suc=pred->lptr;
while(suc->lptr!=NULL)
{
pred=suc;
suc=pred->lptr;
}
pred->lptr=suc->rptr;
suc->lptr=cur->lptr;
suc->rptr=cur->rptr;
q=suc;
}
}
if(d=='L')
{
temp->lptr=q;
}
else
{
temp->rptr=q;
}
}
void preorder(struct tree *p)
{
if(p==NULL)
{
printf("\nNo Root");
exit(1);
}
printf("%d ",p->info);
if(p->lptr!=NULL)
{
preorder(p->lptr);
}
if(p->rptr!=NULL)
{
preorder(p->rptr);
}
}
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi) Show/Hide Program
/*Create a Binary Search Tree and print it's elements in Preorder (iterative code).*/
#include<stdio.h>
#include<conio.h>
struct BinTree
{
struct BinTree *left;
int no;
struct BinTree *right;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BinTree *) malloc(sizeof(struct BinTree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->left != NULL && link->no > temp->no)
link=link->left;
if(link->left == NULL && link->no > temp->no)
{
link->left = temp;
printf("\nNode is Inserted");
return;
}
while(link->right != NULL && link->no < temp->no)
link=link->right;
if(link->right == NULL && link->no < temp->no)
{
link->right = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void preorder(struct BinTree *node)
{
if(node != NULL)
{
printf(" %d",node->no);
preorder(node->left);
preorder(node->right);
}
else
return;
}
void main()
{
int ch;
do
{
clrscr();
printf("1. Insert\n2. PreOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
Treeins();
getch();
break;
case 2:
printf("\nInOrder: ");
preorder(root);
getch();
case 3: exit();
default: printf("You have entered wrong choice\n");
getch();
}
}while(ch!=3);
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Create a Binary Search Tree
//And print it's elements in Preorder (iterative code).
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Preorder(struct BStree *rt)
{
if(rt != NULL)
{
printf(" %d",rt->no);
Preorder(rt->Lsubtree);
Preorder(rt->Rsubtree);
}
else
return;
}
void main()
{
int ch;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. PreOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
printf("\nPreOrder: ");
Preorder(root);
getch();
}
}while(ch!=3);
}
Shared By :Hiren Patel(SRIMCA college-Tarsadi) Show/Hide Program
#include<stdio.h>
#include<conio.h>
struct bstree
{
struct bstree *left;
int val;
struct bstree *right;
}*temp=NULL,*link=NULL,*root=NULL;
void insertpos()
{
if(link==NULL)
{
root=temp;
link=root;
}
else
{
if(temp->val > link->val)
{
if(link->right!=NULL)
{
link=link->right;
insertpos();
}
else
link->right=temp;
}
else if(temp->val < link->val)
{
if(link->left!=NULL)
{
link=link->left;
insertpos();
}
else
link->left=temp;
}
else
{
printf("\nYOU CAN'T ENTER SAME DATA\n");
}
}
}
void insertnode()
{
temp=(struct bstree *)malloc(sizeof(struct bstree));
printf("Enter a Value : ");
scanf("%d",&temp->val);
link=root;
insertpos();
temp->left=NULL;
temp->right=NULL;
}
void preorder(struct bstree * root)
{
if(root!=NULL)
{
printf("%d ",root->val);
preorder(root->left);
preorder(root->right);
}
}
void main()
{
int ch;
clrscr();
do{
clrscr();
printf("1. Insert\n2. Display Node\n3. Exit\nEnter your choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertnode();
printf("\nInserted Successfully...");
getch();
break;
case 2:
printf("\n-----: PREORDER :-----\n");
preorder(root);
getch();
break;
case 3:
break;
default :
printf("\nYou have enter wrong choice");
getch();
}
}while(ch!=3);
}
18. Write a program to create a binary search tree and print it’s elements in postrder..
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi) Show/Hide Program
/*Create a Binary Search Tree and print it's elements in Postorder (iterative code).*/
#include<stdio.h>
#include<conio.h>
struct BinTree
{
struct BinTree *left;
int no;
struct BinTree *right;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BinTree *) malloc(sizeof(struct BinTree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->left != NULL && link->no > temp->no)
link=link->left;
if(link->left == NULL && link->no > temp->no)
{
link->left = temp;
printf("\nNode is Inserted");
return;
}
while(link->right != NULL && link->no < temp->no)
link=link->right;
if(link->right == NULL && link->no < temp->no)
{
link->right = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void postorder(struct BinTree *node)
{
if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf(" %d",node->no);
}
else
return;
}
void main()
{
int ch;
do
{
clrscr();
printf("1. Insert\n2. PostOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
Treeins();
getch();
break;
case 2:
printf("\nInOrder: ");
postorder(root);
getch();
case 3: exit();
default: printf("You have entered wrong choice\n");
getch();
}
}while(ch!=3);
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Create a Binary Search Tree
//And print it's elements in Postorder (iterative code).
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
void Treeins()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Postorder(struct BStree *rt)
{
if(rt != NULL)
{
Postorder(rt->Lsubtree);
Postorder(rt->Rsubtree);
printf(" %d",rt->no);
}
else
return;
}
void main()
{
int ch;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. PostOrder Traversal\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
printf("\nPostOrder: ");
Postorder(root);
getch();
}
}while(ch!=3);
}
Shared By :Hiren Patel(SRIMCA college-Tarsadi) Show/Hide Program
#include<stdio.h>
#include<conio.h>
struct bstree
{
struct bstree *left;
int val;
struct bstree *right;
}*temp=NULL,*link=NULL,*root=NULL;
void insertpos()
{
if(link==NULL)
{
root=temp;
link=root;
}
else
{
if(temp->val > link->val)
{
if(link->right!=NULL)
{
link=link->right;
insertpos();
}
else
link->right=temp;
}
else if(temp->val < link->val)
{
if(link->left!=NULL)
{
link=link->left;
insertpos();
}
else
link->left=temp;
}
else
{
printf("\nYOU CAN'T ENTER SAME DATA\n");
}
}
}
void insertnode()
{
temp=(struct bstree *)malloc(sizeof(struct bstree));
printf("Enter a Value : ");
scanf("%d",&temp->val);
link=root;
insertpos();
temp->left=NULL;
temp->right=NULL;
}
void postorder(struct bstree * root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ",root->val);
}
}
void main()
{
int ch;
clrscr();
do{
clrscr();
printf("1. Insert\n2. Display Node\n3. Exit\nEnter your choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertnode();
printf("\nInserted Successfully...");
getch();
break;
case 2:
printf("\n-----: POSTORDER :-----\n");
postorder(root);
getch();
break;
case 3:
break;
default :
printf("\nYou have enter wrong choice");
getch();
}
}while(ch!=3);
}
19. Write a program to delete an element from a binary search tree.
Shared By : Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Delete an element of Binary Search Tree
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
int flag=0;
void Insert()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp==NULL)
printf("Sorry!! No sufficient Memory");
else
{
printf("Enter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree = temp->Rsubtree = NULL;
if(root == NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link != NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
{
link= link->Lsubtree;
}
if(link->no == temp->no)
{
printf("Sorry!! Duplicate Value can not be Inserted");
return;
}
else if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree=temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no < temp->no)
{
link= link->Rsubtree;
}
if(link->no == temp->no)
{
printf("Sorry!! Duplicate Value can not be Inserted");
return;
}
else if(link->Rsubtree == NULL && link->no < temp->no)
{
link->Rsubtree=temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Delet(struct BStree *rt)
{
if(root == rt)
{
if(root->Lsubtree == NULL)
{
if(root->Rsubtree == NULL)
{
root=NULL;
free(rt);
}
else
{
root=root->Rsubtree;
free(rt);
}
}
else if(root->Rsubtree == NULL)
{
root= root->Lsubtree;
free(rt);
}
else
{
temp=root->Lsubtree;
if(temp->Rsubtree != NULL)
{
while(temp->Rsubtree->Rsubtree != NULL)
temp = temp->Rsubtree;
if(temp->Rsubtree->Lsubtree == NULL)
{
root->no = temp->Rsubtree->no;
free(temp->Rsubtree);
temp->Rsubtree=NULL;
}
else
{
root->no = temp->Rsubtree->no;
rt = temp->Rsubtree;
temp->Rsubtree = temp->Rsubtree->Lsubtree;
free(rt);
}
}
else
{
root->Lsubtree->Rsubtree=root->Rsubtree;
root=root->Lsubtree;
free(rt);
}
}
printf("\nRoot Node is Deleted");
return;
}
else
{
link=root;
while(link->no != rt->no)
{
temp=link;
if(link->no > rt->no)
link=link->Lsubtree;
else
link=link->Rsubtree;
}
if(temp->Lsubtree->no == link->no)
{
if(link->Lsubtree == NULL)
{
if(link->Rsubtree == NULL)
{
temp->Lsubtree=NULL;
free(rt);
}
else
{
temp->Lsubtree=link->Rsubtree;
free(rt);
}
}
else if(link->Rsubtree == NULL)
{
temp->Lsubtree=link->Lsubtree;
free(rt);
}
else
{
link=link->Lsubtree;
if(link->Rsubtree != NULL)
{
while(link->Rsubtree->Rsubtree != NULL)
link = link->Rsubtree;
rt->no = link->Rsubtree->no;
free(link->Rsubtree);
link->Rsubtree=NULL;
}
else if(link->Lsubtree != NULL)
{
link->Rsubtree = rt->Rsubtree;
rt = temp->Lsubtree;
temp->Lsubtree = link;
free(rt);
}
else
{
link->Rsubtree = rt->Rsubtree;
temp->Lsubtree = link;
free(rt);
}
}
}
else if(temp->Rsubtree->no == link->no)
{
if(link->Lsubtree == NULL)
{
if(link->Rsubtree == NULL)
{
temp->Rsubtree=NULL;
free(rt);
}
else
{
temp->Rsubtree=link->Rsubtree;
free(rt);
}
}
else if(link->Rsubtree == NULL)
{
temp->Rsubtree=link->Lsubtree;
free(rt);
}
else
{
link=link->Lsubtree;
if(link->Rsubtree != NULL)
{
while(link->Rsubtree->Rsubtree != NULL)
link = link->Rsubtree;
rt->no = link->Rsubtree->no;
free(link->Rsubtree);
link->Rsubtree=NULL;
}
else if(link->Lsubtree != NULL)
{
link->Rsubtree = rt->Rsubtree;
rt = temp->Rsubtree;
temp->Rsubtree = link;
free(rt);
}
else
{
link->Rsubtree = rt->Rsubtree;
temp->Rsubtree = link;
free(rt);
}
}
}
printf("\nNode is Deleted");
return;
}
}
void Delet_Srch(struct BStree *rt,int val)
{
if(rt != NULL)
{
Delet_Srch(rt->Lsubtree,val);
if(rt->no == val)
{
printf("\n %d %d %d",rt->no,rt->Lsubtree->no,rt->Rsubtree->no);
flag=1;
Delet(rt);
return;
}
Delet_Srch(rt->Rsubtree,val);
}
}
void Inorder(struct BStree *rt)
{
if(rt != NULL)
{
Inorder(rt->Lsubtree);
printf("\n %d %d %d",rt->no,rt->Lsubtree->no,rt->Rsubtree->no);
Inorder(rt->Rsubtree);
}
}
void main()
{
int ch,val;
do
{
do
{
clrscr();
printf("\n1. Insert\n2. Delete\n3. Traversal\n4. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>4);
switch(ch)
{
case 1:
Insert();
getch();
break;
case 2:
printf("\nEnter Value: ");
scanf("%d",&val);
flag=0;
Delet_Srch(root,val);
if(flag==0)
printf("\nValue Does Not Exist");
getch();
break;
case 3:
Inorder(root);
getch();
}
}while(ch!=4);
}
20. Write a program to make another copy of a given binary search tree.
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi) Show/Hide Program
//Write a program to make another copy of a given binary search tree.
#include<stdio.h>
#include<conio.h>
struct BinTree
{
struct BinTree *left;
int val;
struct BinTree *right;
}*root=NULL;
struct CopyTree
{
struct CopyTree *left;
int val;
struct CopyTree *right;
}*nroot=NULL,*ntmp=NULL;
void insert(struct BinTree *node,int no)
{
if(root==NULL)
{
root=(struct BinTree *)malloc(sizeof(struct BinTree));
root->val=no;
root->left=root->right=NULL;
printf("\nRoot node is successfully created\n");
}
else
{
if(no<node->val)
{
if(node->left!=NULL)
insert(node->left,no);
else
{
node->left=(struct BinTree *)malloc(sizeof(struct BinTree));
node->left->val=no;
node->left->left=NULL;
node->left->right=NULL;
printf("\n%d is successfully inserted in tree",node->left->val);
}
}
else if(no>node->val)
{
if(node->right!=NULL)
insert(node->right,no);
else
{
node->right=(struct BinTree *)malloc(sizeof(struct BinTree));
node->right->val=no;
node->right->left=NULL;
node->right->right=NULL;
printf("\n%d is successfully inserted in tree",node->right->val);
}
}
else
printf("You cannot insert duplicate value\n");
}
}
void traverse()
{
int k;
do
{
clrscr();
printf("\n---Traversal Menu---\n");
printf("1.Preorder\n2.Inorder\n3.Postorder\n4.Exit\n");
printf("\nEnter your choice :");
scanf("%d",&k);
switch(k)
{
case 1: printf("\n<--Elements in preorder technique-->\n");
preorder(root);
getch();
break;
case 2: printf("\n<--Elements in inorder technique-->\n");
inorder(root);
getch();
break;
case 3: printf("\n<--Elements in postorder technique-->\n");
postorder(root);
getch();
break;
case 4: break;
default:printf("You have entered invalid choice\n");
getch();
}
}while(k!=4);
}
preorder(struct BinTree *node)
{
if(node!=NULL)
{
printf("%d ",node->val);
preorder(node->left);
preorder(node->right);
}
return;
}
inorder(struct BinTree *node)
{
if(node!=NULL)
{
inorder(node->left);
printf("%d ",node->val);
inorder(node->right);
}
return;
}
postorder(struct BinTree *node)
{
if(node!=NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d ",node->val);
}
return;
}
void copy(struct BinTree *node)
{
if(node!=NULL)
{
if(nroot==NULL)
{
nroot=(struct CopyTree *)malloc(sizeof(struct CopyTree));
nroot=root;
}
else
{
ntmp=(struct CopyTree *)malloc(sizeof(struct CopyTree));
if(ntmp==NULL)
printf("\nNo Sufficient memory");
else
ntmp=node;
copy(node->left);
copy(node->right);
}
}
}
void main()
{
int ch,n;
clrscr();
do
{
clrscr();
printf("1.Insert\n2.Traversal\n3.Make Copy\n4.Exit\n");
printf("Enter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the value :");
scanf("%d",&n);
insert(root,n);
getch();
break;
case 2: traverse();
getch();
break;
case 3: copy(root);
printf("\nCopy is successfully made\n");
printf("\n<---Orginal Copy in inorder--->\n");
inorder(root);
printf("\n\nNew Copy Inorder Traversal :: ");
inorder(nroot);
getch();
break;
case 4: exit();
default:printf("You have enter wrong choice\n");
getch();
}
}while(ch!=4);
getch();
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Create a Copy of Binary Search Tree
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL,*rt_cp=NULL;
void Tree_ins()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void copy(int n)
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
{
printf("\nNo Sufficient Memory!!!");
exit(0);
}
else
{
temp->no=n;
temp->Lsubtree=temp->Rsubtree=NULL;
if(rt_cp==NULL)
{
rt_cp=temp;
}
else
{
link=rt_cp;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
return;
}
}
}
}
}
void Copy_Tree(struct BStree *rt)
{
if(rt != NULL)
{
Copy_Tree(rt->Lsubtree);
copy(rt->no);
Copy_Tree(rt->Rsubtree);
}
}
void Inorder(struct BStree *rt)
{
if(rt != NULL)
{
Inorder(rt->Lsubtree);
printf(" %d",rt->no);
Inorder(rt->Rsubtree);
}
}
void main()
{
int ch;
do
{
do
{ clrscr();
printf("\n1. Insert\n2. Copy\n3. Traversal\n4. Exit");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>4);
switch(ch)
{
case 1:
Tree_ins();
getch();
break;
case 2:
rt_cp=NULL;
Copy_Tree(root);
printf("\nTree is Copied");
printf("\nOriginal Tree InOrder Travarsal: ");
Inorder(root);
printf("\nCopy of Tree InOrder Travarsal: ");
Inorder(rt_cp);
getch();
break;
case 3:
printf("\nInOrder Tree Traversal: \n");
Inorder(root);
getch();
}
}while(ch!=4);
}
21. Write a program to count no of leaf nodes in a given binary tree.
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi) Show/Hide Program
//Write a program to count total number of leaf nodes in binary search tree
#include<stdio.h>
#include<conio.h>
int cnt=0;
struct BinTree
{
struct BinTree *left;
int val;
struct BinTree *right;
}*temp=NULL,*root=NULL,*link=NULL;
void insert()
{
temp=(struct BinTree *)malloc(sizeof(struct BinTree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->val);
temp->left=temp->right=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->left != NULL && link->val > temp->val)
link=link->left;
if(link->left == NULL && link->val > temp->val)
{
link->left = temp;
printf("\nNode is Inserted");
return;
}
while(link->right != NULL && link->val < temp->val)
link=link->right;
if(link->right == NULL && link->val < temp->val)
{
link->right = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void display()
{
int k;
do
{
clrscr();
printf(" Display SubMenu\n1.Inorder\n2.Preorder\n3.Postorder\n4.Breadth First(BFT)\n5.Exit from Submenu\n");
printf("\nEnter your choice :");
scanf("%d",&k);
switch(k)
{
case 1: printf("\nInorder Traversal :: ");
inorder(root);
getch();
break;
case 2: printf("\nPreorder Traversal :: ");
preorder(root);
getch();
break;
case 3: printf("\nPostorder Traversal :: ");
postorder(root);
getch();
break;
case 4: printf("\nBreadth First Traversal :: ");
//breadth(root);
getch();
break;
case 5: break;
default:printf("\nInvalid Choice");
getch();
}
}while(k!=5);
}
inorder(struct BinTree *node)
{
if(node != NULL)
{
inorder(node->left);
printf(" %d",node->val);
inorder(node->right);
}
return;
}
preorder(struct BinTree *node)
{
if(node!=NULL)
{
printf("%d ",node->val);
preorder(node->left);
preorder(node->right);
}
return;
}
postorder(struct BinTree *node)
{
if(node!=NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d ",node->val);
}
return;
}
/*breadth(struct BinTree *node)
{
int i=0,*q;
link=node;
while(link!=NULL)
{
printf("%d ",link->val);
if(link->left!=NULL)
{
q+i=link->left;
i++;
}
if(link->right!=NULL)
{
q+i=link->right;
i++;
}
if(*(q+i)!='\0')
else
link=NULL;
}
} */
cntleaf(struct BinTree *node)
{
if(node!=NULL)
{
cntleaf(node->left);
if(node->left==NULL&&node->right==NULL)
{
printf("%d ",node->val);
cnt++;
}
cntleaf(node->right);
}
return;
}
void main()
{
int ch;
do
{
clrscr();
printf("1.Insert\n2.Display\n3.Count Leaf nodes\n4.Exit\n");
printf("\nEnter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
getch();
break;
case 2: display();
getch();
break;
case 3: printf("\nLeaf nodes are :: ");
cntleaf(root);
printf("\nTotal number of leaf nodes=%d",cnt);
cnt=0;
getch();
break;
case 4: exit();
default:printf("\nInvalid Choice");
getch();
}
}while(ch!=4);
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Count No. of Leaf nodes in a Binary Tree
#include<stdio.h>
struct Btree
{
struct Btree *Lsubtree;
int no;
struct Btree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
struct Btree *q[25];
int first=-1,last=-1;
int CQEmpty()
{
if(first == -1 && last == -1)
return 1;
else
return 0;
}
void CQins(struct Btree *addr)
{
if(first == -1)
first = last = 0;
else if(last == 24)
last=0;
else
last = last + 1;
q[last]=addr;
}
struct Btree * CQdel()
{
struct Btree *t;
t=q[first];
if(first == last)
first=last=-1;
else if(first == 24)
first=0;
else
first = first + 1;
return t;
}
void Treeins()
{
temp=(struct Btree *) malloc(sizeof(struct Btree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
root=temp;
else
{
link=root;
while(link != NULL)
{
if(link->Lsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(link->Lsubtree);
else
{
printf("Cannot Insert !!");
return;
}
}
else
{
link->Lsubtree = temp;
break;
}
if(link->Rsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(link->Rsubtree);
else
{
printf("Cannot Insert !!");
return;
}
}
else
{
link->Rsubtree = temp;
break;
}
if(CQEmpty() == 0)
link=CQdel();
}
}
printf("\nNode is Inserted");
}
}
void cnt_leaf()
{
struct Btree *pnt=root;
int lf=0;
while(pnt != NULL)
{
if(pnt->Lsubtree == NULL && pnt->Rsubtree == NULL)
{
lf++;
}
if(pnt->Lsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Lsubtree);
else
return;
}
if(pnt->Rsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Rsubtree);
else
return;
}
if(CQEmpty() == 0)
pnt=CQdel();
else
pnt=NULL;
}
printf("\nThe no. of Leaf Nodes in a Binary Tree are %d",lf);
}
void main()
{
int ch;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. Count Leafs\n");
printf("3. Exit\nEnter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
first = last = -1;
cnt_leaf();
getch();
}
}while(ch!=3);
}
22. Write a program to search an element in a given binary search tree.
Shared By :Hiral Prajapati(SRIMCA college-Tarsadi) Show/Hide Program
//Write a program to search an element in a given binary search tree.
#include<stdio.h>
#include<conio.h>
int cnt=0;
struct BinTree
{
struct BinTree *left;
int val;
struct BinTree *right;
}*root=NULL,*temp=NULL;
void insert(struct BinTree *node,int no)
{
if(root==NULL)
{
root=(struct BinTree *)malloc(sizeof(struct BinTree));
root->val=no;
root->left=root->right=NULL;
printf("\nRoot node is successfully created\n");
}
else
{
if(no<node->val)
{
if(node->left!=NULL)
insert(node->left,no);
else
{
node->left=(struct BinTree *)malloc(sizeof(struct BinTree));
node->left->val=no;
node->left->left=NULL;
node->left->right=NULL;
printf("\n%d is successfully inserted in tree",node->left->val);
}
}
else if(no>node->val)
{
if(node->right!=NULL)
insert(node->right,no);
else
{
node->right=(struct BinTree *)malloc(sizeof(struct BinTree));
node->right->val=no;
node->right->left=NULL;
node->right->right=NULL;
printf("\n%d is successfully inserted in tree",node->right->val);
}
}
else
printf("You cannot insert duplicate value\n");
}
}
void traverse()
{
int k;
do
{
clrscr();
printf("\n---Traversal Menu---\n");
printf("1.Preorder\n2.Inorder\n3.Postorder\n4.Exit\n");
printf("\nEnter your choice :");
scanf("%d",&k);
switch(k)
{
case 1: printf("\n<--Elements in preorder technique-->\n");
preorder(root);
getch();
break;
case 2: printf("\n<--Elements in inorder technique-->\n");
inorder(root);
getch();
break;
case 3: printf("\n<--Elements in postorder technique-->\n");
postorder(root);
getch();
break;
case 4: break;
default:printf("You have entered invalid choice\n");
getch();
}
}while(k!=4);
}
preorder(struct BinTree *node)
{
if(node!=NULL)
{
printf("%d ",node->val);
preorder(node->left);
preorder(node->right);
}
return;
}
inorder(struct BinTree *node)
{
if(node!=NULL)
{
inorder(node->left);
printf("%d ",node->val);
inorder(node->right);
}
return;
}
postorder(struct BinTree *node)
{
if(node!=NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d ",node->val);
}
return;
}
void search(struct BinTree *node,int no)
{
if(node!=NULL)
{
if(node->val==no)
cnt=1;
else
{
search(node->left,no);
search(node->right,no);
}
}
}
void main()
{
int ch,n;
clrscr();
do
{
clrscr();
printf("1.Insert\n2.Traversal\n3.Search\n4.Exit\n");
printf("Enter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the value :");
scanf("%d",&n);
insert(root,n);
getch();
break;
case 2: traverse();
getch();
break;
case 3: printf("Which element you want to search? :");
scanf("%d",&n);
search(root,n);
if(cnt==1)
{
printf("\nValue is found in the tree");
cnt=0;
}
else
printf("\nValue is not found in the tree");
getch();
break;
case 4: exit();
default:printf("You have enter wrong choice\n");
getch();
}
}while(ch!=4);
getch();
}
Shared By :Sonam Patel(SRIMCA college-Tarsadi) Show/Hide Program
//Search an element in a Binary Search Tree
#include<stdio.h>
struct BStree
{
struct BStree *Lsubtree;
int no;
struct BStree *Rsubtree;
}*root=NULL,*link=NULL,*temp=NULL;
struct BStree *q[25];
int first,last;
int CQEmpty()
{
if(first == -1 && last == -1)
return 1;
else
return 0;
}
void CQins(struct BStree *addr)
{
if(first == -1)
first = last = 0;
else if(last == 24)
last=0;
else
last = last + 1;
q[last]=addr;
}
struct BStree * CQdel()
{
struct BStree *t;
t=q[first];
if(first == last)
first=last=-1;
else if(first == 24)
first=0;
else
first = first + 1;
return t;
}
void Treeins()
{
temp=(struct BStree *) malloc(sizeof(struct BStree));
if(temp == NULL)
printf("\nNo Sufficient Memory!!!");
else
{
printf("\nEnter Value: ");
scanf("%d",&temp->no);
temp->Lsubtree=temp->Rsubtree=NULL;
if(root==NULL)
{
root=temp;
printf("\nNode is Inserted");
}
else
{
link=root;
while(link!=NULL)
{
while(link->Lsubtree != NULL && link->no > temp->no)
link=link->Lsubtree;
if(link->Lsubtree == NULL && link->no > temp->no)
{
link->Lsubtree = temp;
printf("\nNode is Inserted");
return;
}
while(link->Rsubtree != NULL && link->no <= temp->no)
link=link->Rsubtree;
if(link->Rsubtree == NULL && link->no <= temp->no)
{
link->Rsubtree = temp;
printf("\nNode is Inserted");
return;
}
}
}
}
}
void Search(int n)
{
struct BStree *pnt=root;
first=-1,last=-1;
while(pnt != NULL)
{
if(pnt->no == n)
{
printf("\n%d is Exist in the Binary Search Tree",n);
break;
}
if(pnt->Lsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Lsubtree);
else
return;
}
if(pnt->Rsubtree != NULL)
{
if(last - first != 24 && first - last != 1)
CQins(pnt->Rsubtree);
else
return;
}
if(CQEmpty() == 0)
pnt=CQdel();
else
pnt=NULL;
}
if(pnt==NULL)
printf("\n%d is not Exist in the Binary Search Tree",n);
}
void main()
{
int ch,n;
do
{ do
{ clrscr();
printf("\n1. Insert\n2. Search\n3. Exit\n");
printf("Enter Your Choice: ");
scanf("%d",&ch);
}while(ch<1 || ch>3);
switch(ch)
{ case 1:
Treeins();
getch();
break;
case 2:
printf("\nEnter the value which you want to search: ");
scanf("%d",&n);
Search(n);
getch();
}
}while(ch!=3);
}
23. Write a program to Generate Min-heap and Max-heap (Insertion and Deletion )
Share This Program..
send it gtumca@gmail.com
with your name - college name..
and share what you want ... at same mail id...
Thanx in advance...
Be connected...
D_i_Z
Shared By :Your Name Show/Hide Program
24. Write a program for Insertion of a node in m-way tree (B-Tree/B+-Tree)
Share This Program..
send it gtumca@gmail.com
with your name - college name..
and share what you want ... at same mail id...
Thanx in advance...
Be connected...
D_i_Z
Shared By :Your Name Show/Hide Program