Data Structures Using C++

Data Structure Using C++ Lab Manual

Subject Code: 21EC584
V Semester

DEPARTMENT OF ELECTRONICS AND

COMMUNICATION ENGINEERING

1
Data Structures Using C++

EXPERIMENTS
S.No Content
1 Write a C++ program that uses functions to perform the following:
a) Create a singly linked list of integers.
b) Delete a given integer from the above linked list.
c) Display the contents of the above list after deletion.

2 Write a template based C++ program that uses functions to perform the
following:
a) Create a doubly linked list of elements.
b) Delete a given element from the above doubly linked list.
c) Display the contents of the above list after deletion.

3 Write a C++ program that uses stack operations to convert a given infix
expression into its postfix equivalent, Implement the stack using an array.
4 Write a C++ program to implement a double ended queue ADT using an array,
Using a doubly linked list.
5 Write a C++ program that uses function templates to perform the following:
a) Search for a key element in a list of elements using linear search.
b) Search for a key element in a list of sorted elements using binary search.
6 Write a C++ program that implements Insertion sort algorithm to arrange a list
of integers in ascending order.
7 Write a template based C++ program that implements selection sort algorithm
to arrange a list of elements in descending order.
8 Write a template based C++ program that implements Quick sort algorithm to
arrange a list of elements in ascending order.
9 Write a C++ program that implements Heap sort algorithm for sorting a list of
integers in ascending order.
10 Write a C++ program that implements Radix sort algorithm for sorting a list of
integers in ascending order.
11 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.
12 Write a C++ program that uses functions to perform the following:
a) Create a binary search tree of integers.
b) Search for an integer key in the above binary search tree non recursively.
c) Search for an integer key in the above binary search tree recursively.

2
Data Structures Using C++

3
 Data Structures Using C++

1. Write a C++ program that uses functions to perform the following:

a) Create a singly linked list of integers.
b) Delete a given integer from the above linked list.
c) Display the contents of the above list after deletion.

C++ Program to Implement Singly Linked List

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*start;

/*
* Class Declaration
*/
class single_llist
{
public:
node* create_node(int);
void insert_begin();
void insert_pos();
void insert_last();
void delete_pos();
void sort();
void search();
void update();
void reverse();
void display();
single_llist()
{
start = NULL;
}
};

4
Data Structures Using C++

/*
* Main :contains menu
*/
main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
while (1)
{
cout<<endl<<" "<<endl;
cout<<endl<<"Operations on singly linked
list"<<endl; cout<<endl<<" "<<endl;
cout<<"1.Insert Node at beginning"<<endl;
cout<<"2.Insert node at last"<<endl;
cout<<"3.Insert node at position"<<endl;
cout<<"4.Sort Link List"<<endl;
cout<<"5.Delete a Particular Node"<<endl;
cout<<"6.Update Node Value"<<endl;
cout<<"7.Search Element"<<endl;
cout<<"8.Display Linked List"<<endl;
cout<<"9.Reverse Linked List "<<endl;
cout<<"10.Exit "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Inserting Node at Beginning: "<<endl;
sl.insert_begin();
cout<<endl;
break;
case 2:
cout<<"Inserting Node at Last: "<<endl;
sl.insert_last();
cout<<endl;
break;
case 3:
cout<<"Inserting Node at a given
position:"<<endl; sl.insert_pos();
cout<<endl;
break;
case 4:
cout<<"Sort Link List: "<<endl;
sl.sort();

5
Data Structures Using C++

cout<<endl;
break;
case 5:
cout<<"Delete a particular node:
"<<endl; sl.delete_pos();
break;
case 6:
cout<<"Update Node Value:"<<endl;
sl.update();
cout<<endl;
break;
case 7:
cout<<"Search element in Link List: "<<endl;
sl.search();
cout<<endl;
break;
case 8:
cout<<"Display elements of link list"<<endl;
sl.display();
cout<<endl;
break;
case 9:
cout<<"Reverse elements of Link List"<<endl;
sl.reverse();
cout<<endl;
break;
case 10:
cout<<"Exiting..."<<endl;
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}

/*
* Creating Node
*/
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;

6
Data Structures Using C++

return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}

/*
* Inserting element in beginning
*/
void single_llist::insert_begin()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
cout<<"Element Inserted at beginning"<<endl;
}

/*
* Inserting Node at last
*/
void single_llist::insert_last()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)

7
Data Structures Using C++

{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}

/*
* Insertion of node at a given position
*/
void single_llist::insert_pos()
{
int value, pos, counter = 0;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s, *ptr;
temp = create_node(value);
cout<<"Enter the postion at which node to be inserted:
"; cin>>pos;
int i;
s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos == 1)
{
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (pos > 1 && pos <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{

8
Data Structures Using C++

ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<"Positon out of range"<<endl;
}
}

/*
* Sorting Link List
*/
void single_llist::sort()
{
struct node *ptr, *s;
int value;
if (start == NULL)
{
cout<<"The List is empty"<<endl;
return;
}
ptr = start;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->info > s->info)
{
value = ptr->info;
ptr->info = s->info;
s->info = value;
}
}
ptr = ptr->next;
}
}

/*
* Delete element at a given position
*/
void single_llist::delete_pos()
{
int pos, i, counter = 0;

9
Data Structures Using C++

if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the position of value to be deleted: ";
cin>>pos;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start = s->next;
}
else
{
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter)
{
s = start;
for (i = 1;i < pos;i++)
{
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else
{
cout<<"Position out of range"<<endl;
}
free(s);
cout<<"Element Deleted"<<endl;
}
}

/*
* Update a given Node
*/
void single_llist::update()
{
int value, pos, i;
if (start == NULL)

10
Data Structures Using C++

{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the node postion to be updated:
"; cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start->info = value;
}
else
{
for (i = 0;i < pos - 1;i++)
{
if (s == NULL)
{
cout<<"There are less than "<<pos<<" elements";
return;
}
s = s->next;
}
s->info = value;
}
cout<<"Node Updated"<<endl;
}

/*
* Searching an element
*/
void single_llist::search()
{
int value, pos = 0;
bool flag = false;
if (start ==
NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the value to be searched:
"; cin>>value;
struct node *s;
s = start;
11
Data Structures Using C++

while (s != NULL)
{
pos++;
if (s->info == value)
{
flag = true;
cout<<"Element "<<value<<" is found at position "<<pos<<endl;
}
s = s->next;
}
if (!flag)
cout<<"Element "<<value<<" not found in the list"<<endl;
}

/*
* Reverse Link List
*/
void single_llist::reverse()
{
struct node *ptr1, *ptr2, *ptr3;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
if (start->next == NULL)
{
return;
}
ptr1 = start;
ptr2 = ptr1->next;
ptr3 = ptr2->next;
ptr1->next = NULL;
ptr2->next = ptr1;
while (ptr3 != NULL)
{
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
start = ptr2;
}

/*
* Display Elements of a link list

12
Data Structures Using C++

*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = start;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->info<<"->";
temp = temp->next;
}
cout<<"NULL"<<endl;
}

Output:

Operations on singly linked list

1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
The List is Empty.
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value

13
Data Structures Using C++

7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 5
Delete a particular node:
List is empty
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 6
Update Node Value:
List is empty
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 7
Search element in Link List:
List is empty
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List

14
Data Structures Using C++

5.Delete a Particular Node

6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 3
Inserting Node at a given position:
Enter the value to be inserted: 1010
Enter the postion at which node to be inserted: 5
Positon out of range
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 1
Inserting Node at Beginning:
Enter the value to be inserted: 100
Element Inserted at beginning
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 1
Inserting Node at Beginning:
Enter the value to be inserted: 200
Element Inserted at beginning

15
Data Structures Using C++

Operations on singly linked list

1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
200->100->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 2
Inserting node at last:
Enter the value to be inserted: 50
Element Inserted at last
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List

16
Data Structures Using C++

10.Exit
Enter your choice : 2
Inserting node at last:
Enter the value to be inserted: 150
Element Inserted at last
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
200->100->50->150->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 3
Inserting node at a given position:
Enter the value to be inserted: 1111
Enter the position at which node to be inserted: 4
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List

17
Data Structures Using C++

5.Delete a Particular Node

6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
200->100->50->1111->150->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 3
Inserting node at a given position:
Enter the value to be inserted: 1010
Enter the position at which node to be inserted: 100
Position out of range
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
200->100->50->1111->150->NULL

18
Data Structures Using C++

Operations on singly linked list

1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 5
Delete a Particular node:
Enter the position of value to be deleted: 1
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
100->50->1111->150->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit

19
Data Structures Using C++

Enter your choice : 6

Update Node Value:
Enter the node position to be updated: 1
Enter the new value: 1010
Node Updated
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
1010->50->1111->150->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 7
Search element in Link List:
Enter the value to be searched: 50
Element 50 is found at position 2
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List

20
Data Structures Using C++

5.Delete a Particular Node

6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 9
Reverse elements of Link List
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
150->1111->50->1010->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5.Delete a Particular Node
6.Update Node Value
7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 4
Sort Link List:
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position

21
Data Structures Using C++

4. Sort Link List

5. Delete a Particular
Node 6.Update Node
Value 7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 8
Display elements of link list
Elements of list are:
50->150->1010->1111->NULL
Operations on singly linked list
1.Insert Node at beginning
2.Insert node at last
3.Insert node at position
4.Sort Link List
5. Delete a Particular
Node 6.Update Node
Value 7.Search Element
8.Display Linked List
9.Reverse Linked List
10.Exit
Enter your choice : 10

Viva Questions:

1. List the differences between the linked array and linked list.
2. What is meant by single linked list.
3. What type of memory allocation is referred for Linked lists?
4. name the types of Linked Lists?
5. Mention what are the applications of Linked Lists?
6. List the disadvantages of single linked list.

22
 Data Structures Using C++

2. Write a template based C++ program that uses functions to perform the following:
a) Create a doubly linked list of elements.
b) Delete a given element from the above doubly linked list.
c) Display the contents of the above list after deletion.

C++ Program to Implement Doubly Linked List

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
/*
* Node Declaration
*/
using namespace std;
struct node
{
int info;
struct node *next;
struct node *prev;
}*start;

/*
Class Declaration
*/
class double_llist
{
public:
void create_list(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_dlist();
void count();

23
Data Structures Using C++

void reverse();
double_llist()
{
start = NULL;
}
};

/*
* Main: Conatins Menu
*/
int main()
{
int choice, element, position;
double_llist dl;
while (1)
{
cout<<endl<<"---------------------------"<<endl;
cout<<endl<<"Operations on Doubly linked list"<<endl;
cout<<endl<<"---------------------------"<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at begining"<<endl;
cout<<"3.Add after
position"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Display"<<endl;
cout<<"6.Count"<<endl;
cout<<"7.Reverse"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch ( choice )
{
case 1:
cout<<"Enter the element: ";
cin>>element;
dl.create_list(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
dl.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
24
Data Structures Using C++

cout<<"Insert Element after postion: ";

cin>>position;
dl.add_after(element, position);
cout<<endl;
break;
case 4:
if (start == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
dl.delete_element(element);
cout<<endl;
break;
case 5:
dl.display_dlist();
cout<<endl;
break;
case 6:
dl.count();
break;
case 7:
if (start == NULL)
{
cout<<"List empty,nothing to
reverse"<<endl; break;
}
dl.reverse();
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}

/*
* Create Double Link List
*/
void double_llist::create_list(int value)
{

25
Data Structures Using C++

struct node *s, *temp;

temp = new(struct
node); temp->info =
value; temp->next =
NULL;
if (start == NULL)
{
temp->prev = NULL;
start = temp;
}
else
{
s = start;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}

/*
* Insertion at the beginning
*/
void double_llist::add_begin(int value)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct
node); temp->prev =
NULL; temp->info =
value; temp->next =
start;
start->prev = temp;
start = temp;
cout<<"Element Inserted"<<endl;
}

/*
* Insertion of element at a particular position
*/
void double_llist::add_after(int value, int pos)
{
if (start == NULL)
26
Data Structures Using C++

27
Data Structures Using C++

cout<<"First Create the list."<<endl;

return;
}
struct node *tmp, *q;
int i;
q = start;
for (i = 0;i < pos - 1;i++)
{
q = q->next;
if (q == NULL)
{
cout<<"There are less than ";
cout<<pos<<" elements."<<endl;
return;
}
}
tmp = new(struct node);
tmp->info = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next =
NULL; tmp->prev
= q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout<<"Element Inserted"<<endl;
}

/*
* Deletion of element from the list
*/
void double_llist::delete_element(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (start->info == value)
{
tmp = start;
start = start->next;
start->prev = NULL;
28
Data Structures Using C++

cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = start;
while (q->next->next != NULL)
{
/*Element deleted in between*/
if (q->next->info == value)
{
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = q->next;
}
/*last element deleted*/
if (q->next->info == value)
{
tmp = q->next;
free(tmp);
q->next = NULL;
cout<<"Element Deleted"<<endl;
return;
}
cout<<"Element "<<value<<" not found"<<endl;
}

/*
* Display elements of Doubly Link List
*/
void double_llist::display_dlist()
{
struct node *q;
if (start == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = start;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{

29
Data Structures Using C++

cout<<q->info<<" <-> ";

q = q->next;
}
cout<<"NULL"<<endl;
}

/*
* Number of elements in Doubly Link List
*/
void double_llist::count()
{
struct node *q = start;
int cnt = 0;
while (q != NULL)
{
q = q->next;
cnt++;
}
cout<<"Number of elements are: "<<cnt<<endl;
}

/*
* Reverse Doubly Link List
*/
void double_llist::reverse()
{
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while (p2 != NULL)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev;
}
start = p1;
cout<<"List Reversed"<<endl;
}

30
Data Structures Using C++

Output:
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 2
Enter the element: 100
First Create the list.
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 3
Enter the element: 200
Insert Element after postion: 1
First Create the list.
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 4
List empty,nothing to delete
Operations on Doubly linked list

31
Data Structures Using C++

1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
List empty,nothing to display
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 6
Number of elements are: 0
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 7
List empty,nothing to reverse
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse

32
Data Structures Using C++

8.Quit
Enter your choice : 1
Enter the element: 100
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
100 <-> NULL
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 2
Enter the element: 200
Element Inserted
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> NULL

33
Data Structures Using C++

Operations on Doubly linked list

1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 3
Enter the element: 50
Insert Element after postion: 2
Element Inserted
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 50 <-> NULL
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 3
Enter the element: 150
Insert Element after postion: 3
Element Inserted
Operations on Doubly linked list

34
Data Structures Using C++

1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 50 <-> 150 <-> NULL
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 6
Number of elements are: 4
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 4
Enter the element for deletion: 50
Element Deleted
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete

35
Data Structures Using C++

5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 150 <-> NULL
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 6
Number of elements are: 3
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 7
List Reversed
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :

36
Data Structures Using C++

150 <-> 100 <-> 200 <-> NULL

Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 3
Enter the element: 200
Insert Element after postion: 100
There are less than 100 elements.
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 4
Enter the element for deletion: 150
Element Deleted
Operations on Doubly linked list
1.Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 5
The Doubly Link List is :
100 <-> 200 <-> NULL
Operations on Doubly linked list

37
Data Structures Using C++

1. Create Node
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 8

Viva Questions :

1. What is the double linked list?

2. What are the applications of double linked list?
3. What are the advantages of double linked list over single linked list?
4. How to add the new node in middle of the double linked list?
5. What are the memory allocation functions to create the double linked list?

38
Data Structures Using C++

3. Write a C++ program that uses stack operations to convert a given infix expression into
its postfix equivalent, Implement the stack using an array.

Source Code:
#include <iostream.h>
#include <string.h>
#include <ctype.h>
const int MAX = 50 ;
class infix
{
private :
char target[MAX], stack[MAX] ;
char *s, *t ;
int top ;
public :
infix( ) ;
void setexpr ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void show( ) ;
};
infix :: infix( )
{
top = -1 ;
strcpy ( target, "" ) ;
strcpy ( stack, "" ) ;

39
Data Structures Using C++

t = target ;
s = "" ;
}
void infix :: setexpr ( char *str )
{
s = str ;
}
void infix :: push ( char c )
{
if ( top == MAX )
cout << "\nStack is full\n" ;
else
{
top++ ;
stack[top] = c ;
}
}
char infix :: pop( )
{
if ( top == -1 )
{
cout << "\nStack is empty\n" ;
return -1 ;
}
else
{
char item = stack[top] ;
top-- ;
return item ;
}
}
void infix :: convert( )
{
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;

40
Data Structures Using C++

t++ ;
}
}
if ( *s == '(' )
{
push ( *s ) ;
s++ ;
}
char opr
;
if ( *s == '*' || *s == '+' || *s == '/' || *s == '%' || *s == '-' || *s == '$' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) >= priority ( *s ) )
{
*t = opr ;
t++ ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == ')' )
{
opr = pop( ) ;
while ( ( opr ) != '(' )
{
*t = opr ;
t++ ;
opr = pop( ) ;
} s+
+;
}
}
while ( top != -1 )
{
;

}
*t = '\0'
41
 Data Structures Using C++

char opr = pop( ) ;

*
t

o
p
r

t
+
+

42
Data Structures Using C++

}
int infix :: priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void infix :: show( )
{
cout << target ;
}
void main( )
{
char expr[MAX] ;
infix q ;

cout << "\nEnter an expression in infix form: " ;

cin.getline ( expr, MAX ) ;

q.setexpr ( expr ) ;
q.convert( ) ;

cout << "\nThe postfix expression is: " ;

q.show( ) ;
}
Output:
Enter the postfix experssion : a+b*c
Post fix expression is : abc*+
Enter the postfix experssion : a+(b+c*d)*f
Post fix expression is : abcd*+f*+
Enter the postfix experssion : a+(b*c+d)*f
Post fix expression is : abc*d+f*+

Viva Questions:
1. What are the applications of stack?
2. List the types of conversions.
3. What is the inorder?
4. What is the postorder?

43
Data Structures Using C++

4. Write a C++ program to implement a double ended queue ADT using an array, using
a doubly linked list.

Source Code:
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;

class queue
{
int queue1[5];
int rear,front;
public:
queue()
{
rear=-1;
front=-1;
}
void insert(int x)
{
if(rear > 4)
{
cout <<"queue over flow";
front=rear=-1;
return;
}
queue1[++rear]=x;
cout <<"inserted" <<x;
}
void delet()
{
if(front==rear)

{
cout <<"queue under flow";
return;
}
cout <<"deleted" <<queue1[++front];
}
void display()
{
if(rear==front)
{
cout <<" queue empty";
return;
44
Data Structures Using C++

}
for(int i=front+1;i<=rear;i++)
cout <<queue1[i]<<" ";
}
}

main()
{
int ch;
queue qu;
while(1)
{
cout <<"\n1.insert 2.delet 3.display 4.exit\nEnter ur choice";
cin >> ch;
switch(ch)
{
case 1: cout <<"enter the element";
cin >> ch;
qu.insert(ch);
break;
case 2: qu.delet(); break;
case 3: qu.display();break;
case 4: exit(0);
}
}
return (0);
}

Output:
1.insert 2.delet 3.display 4.exit
Enter ur choice1
enter the element21
inserted21

1.insert 2.delet 3.display 4.exit

Enter ur choice1
enter the element22
inserted22

1.insert 2.delet 3.display 4.exit

Enter ur choice1
enter the element16
inserted16

1.insert 2.delet 3.display 4.exit

Enter ur choice3
21 22 16
45
Data Structures Using C++

1.insert 2.delet 3.display 4.exit

Enter ur choice2
deleted21

1.insert 2.delet 3.display 4.exit

Enter ur choice3
22 16

1.insert 2.delet 3.display 4.exit

Enter ur choice

i) Linked List

AIM: To implement a Double ended Queue using Linked List

Source Code:

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

class node
{
public:
int data;
class node *next;
class node *prev;
};

class dqueue: public node

{
node *head,*tail;
int top1,top2;
public:
dqueue()
{
top1=0;

46
Data Structures Using C++

top2=0;
head=NULL;
tail=NULL;
}
void push(int x){
node *temp;
int ch;
if(top1+top2 >=5)
{
cout <<"dqueue overflow";
return ;
}
if( top1+top2 == 0)
{
head = new
node; head-
>data=x;
head->next=NULL;
head->prev=NULL;
tail=head;
top1++;
}
else
{
cout <<" Add element 1.FIRST 2.LAST\n enter ur choice:";
cin >> ch;

if(ch==1)
{
top1++;
temp=new node;
temp->data=x;
temp->next=head;
temp->prev=NULL;
head->prev=temp;
head=temp;
}
else
{
top2++;
temp=new node;
temp->data=x;
temp->next=NULL;
temp->prev=tail;
tail->next=temp;
tail=temp;
47
Data Structures Using C++

}
}
void pop()
{
int ch;
cout <<"Delete 1.First Node 2.Last Node\n Enter ur choice:";
cin >>ch;
if(top1 + top2 <=0)
{
cout <<"\nDqueue under flow";
return;
}
if(ch==1)
{
head=head->next;
head->prev=NULL;
top1--;
}
else
{
top2--;
tail=tail->prev;
tail->next=NULL;
}
}

void display()
{
int ch;
node *temp;
cout <<"display from 1.Staring 2.Ending\n Enter ur choice";
cin >>ch;
if(top1+top2 <=0)
{
cout <<"under flow";
return ;
}
if (ch==1)
{
temp=head;
while(temp!=NULL)
{
cout << temp->data <<" ";
temp=temp->next;

48
Data Structures Using C++

}
}
else
{
temp=tail;
while( temp!=NULL)
{
cout <<temp->data << " ";
temp=temp->prev;
}
}
}
};

main()
{
dqueue d1;
int ch;
while (1){
cout <<"1.INSERT 2.DELETE 3.DISPLAU 4.EXIT\n Enter ur choice:";
cin >>ch;
switch(ch)
{
case 1: cout <<"enter element";
cin >> ch;
d1.push(ch); break;
case 2: d1.pop(); break;
case 3: d1.display(); break;
case 4: exit(1);
}
}}

OUTPUT

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:1
enter element4

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:1
enter element5
Add element 1.FIRST 2.LAST
enter ur choice:1

49
Data Structures Using C++

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:1
enter element6
Add element 1.FIRST 2.LAST
enter ur choice:2

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:3
display from 1.Staring 2.Ending
Enter ur choice1
546

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:2
Delete 1.First Node 2.Last Node
Enter ur choice:1

1.INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:3
display from 1.Staring 2.Ending

Enter ur choice1
46

1. INSERT 2.DELETE 3.DISPLAU 4.EXIT

Enter ur choice:4

Viva Questions:
1. What is the double ended queue?
2. What are the applications of double ended queue?
3. Which data structure is used for double ended queue?
4. List the advantages of double ended queue over single queue.
5. List the disadvantages of double ended queue.

50
Data Structures Using C++

51
Data Structures Using C++

5. .Write a C++ program that uses function templates to perform the following:
a) Search for a key element in a list of elements using linear search.
b) Search for a key element in a list of sorted elements using binary search.

a) Search for a key element in a list of elements using linear search.

Source Code:

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int arr[10], i, num, n, c=0, pos;
cout<<"Enter the array size : ";
cin>>n;
cout<<"Enter Array Elements : ";
for(i=0; i<n; i++)
{
cin>>arr[i];
}
cout<<"Enter the number to be search :
"; cin>>num;
for(i=0; i<n; i++)
{
if(arr[i]==num)
{
c=1;
pos=i+1;
break;
}
}
if(c==0)
{
cout<<"Number not found..!!";
}

else

{
Cout<<num<<”found at position”<<pos;
}
getch();

52
 Data Structures Using C++

Output:
Enter the array size 5
Enter array elements :
4
5
9
1
4
Enter the number to search: 9
Found at position 3

53
Data Structures Using C++

b) Search for a key element in a list of sorted elements using binary search.

Source Code:
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20], i, n, key, low, high, mid;
clrscr();
printf(“Enter the array elements in ascending order”);
for(i = 0; i < n; i++)
{
scanf(“%d”, &a[i]);
}
printf(“Enter the key element\n”);
scanf(“%d”, &key);
low = 0;
high = n - 1;
while(high >= low)
{
mid = (low + high) / 2;
if(key == a[mid])
break;
else
{
if(key > a[mid])
low = mid + 1;
else
high = mid - 1;
}
}
if(key == a[mid])
printf(“The key element is found at location %d”, mid + 1);
else
printf(“the key element is not found”);
getch();
}
Output:
Enter the size of the array 7
Enter the array elements in ascending order 23 45 68 90 100 789 890
Enter the key element 789
The key Element is found at location 6
Viva Questions:
1. What is meant by linear search?
2. What is meant by binary search?
3. What are the applications of binary search?
4. What is the time complexity of liner search?
54
 Data Structures Using C++

6. Write a C++ program that implements Insertion sort algorithm to arrange a list of integers in
ascending order.

Source Code:

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

template<class T>
void isort(T a[],int n)
{
int i;
for(i=1;i<n;i++)
{
T t=a[i];
int j;
for(j=i-1;j>=0&&t<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=t;
}
}

void main()
{
int a[100],i,n;
cout<<"Enter number of elements :
"; cin>>n;
cout<<"Enter elements (Use Spacebar as Separator)\n";
for(i=0;i<n;i++)
{

cin>>a[i];
}
isort(a,n);
cout<<"After sorting the elements are\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<"\n";
}
system("pause");

55
Data Structures Using C++

Output:

Enter number of elements : 5

Enter elements (Use Spacebar as Separator)
9
7
5
45
24
After sorting the elements are

5
7
9
24
45

Viva Questions:

1. List the types of sorting.

2. What is the best case time complexity of insertion sort?
3. What is the average case time complexity of insertion sort?
4. What is the worst case time complexity of insertion sort?
5. Give the example to insertion sort.

56
 Data Structures Using C++

7.Write a template based C++ program that implements selection sort algorithm to arrange a list of
elements in descending order.

Source Code:

#include<iostream>

#include<stdio.h>

int main()
{
int i,j,n,loc,temp,min,a[30];
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";

for(i=0;i<n;i++)
{
cin>>a[i];
}

for(i=0;i<n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<n;j++)

{
if(min>a[j])
{
min=a[j];
loc=j;
}
}

temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}

cout<<"\nSorted list is as follows\n";

for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}

57
Data Structures Using C++

return 0;
}

Output:
Enter the number of elements: 6
Enter the elements
18 3 10 7 8 1
Sorted list is as follows
1 3 7 8 10 18

Viva Questions:

1. What is the best case time complexity of selection sort?

2. What is the average case time complexity of selection sort?
3. What is the worst case time complexity of selection sort?
4. Give the example to selection sort.

58
Data Structures Using C++

8. Write a template based C++ program that implements Quick sort algorithm to arrange a list of
elements in ascending order.

Source Code:

#include<iostream>
#include<conio.h>
#include<stdio.h>

//Function for partitioning array

int part(int low,int high,int *a)
{
int i,h=high,l=low,p,t; //p==pivot
p=a[low];
while(low<high)
{
while(a[l]<p)
{
l++;
}
while(a[h]>p)
{
h--;
}
if(l<h
)
{ t=a[l];
a[l]=a[h];
a[h]=t;

}
else
{
t=p;
p=a[l];
a[l]=t;
break;
}
}
return h;
}

void quick(int l,int h,int *a)

{
59
 Data Structures Using C++

int index,i;
if(l<h)
{
index=part(l,h,a);
quick(l,index-1,a);
quick(index+1,h,a);

}
}

int main()
{
int a[100],n,l,h,i;
cout<<"Enter number of elements:";
cin>>n;
cout<<"Enter the elements (Use Space As A Separator):";
for(i=0;i<n;i++)
cin>>a[i];
cout<<"\nInitial Array:\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
h=n-1;
l=0;
quick(l,h,a); cout<<"\
nAfter Sorting:\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
getch();
return 0;
}
Output:
Enter number of elements: 6
Enter the elements : 8 6 54 2 1
Initial Array:
8 6 54 2 1
After Sorting:
124568

Viva Questions:

1. What is the best case time complexity of Quick sort?

2. What is the average case time complexity of quick sort?
3. What is the worst case time complexity of quick sort?
60
Data Structures Using C++

4. What is the methodology followed by quick sort?

61
 Data Structures Using C++

9.Write a C++ program that implements Heap sort algorithm for sorting a list of integers in
ascending order.

Source Code:
/*
* C++ Program to Implement Heap Sort
*/
#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void heapsort(int *a, int n)
{
int i, temp;

for (i = n; i >= 2; i--)

{
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
62
 Data Structures Using C++

for(i = n/2; i >= 1; i--)

{
max_heapify(a, i, n);
}
}

int main()
{
int n, i, x;
cout<<"enter no of elements of array\n";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<"enter element"<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
heapsort(a, n);
cout<<"sorted output\n";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();
}

Output
enter no of elements of array
7
enter element1
34
enter element2
45
enter element3
12
enter element4

40
enter element5
6
enter element6
75
enter element7
36
63
Data Structures Using C++

sorted output
6
12
34
36
40
45
75

Viva Questions:

1. What is meant by heap sort?

2. What is the best case time complexity of Heap sort?
3. What is the average case time complexity of heap sort?
4. What is the worst case time complexity of heap sort?
5. List the applications of heap sort.

64
Data Structures Using C++

10. Write a C++ program that implements Radix sort algorithm for sorting a list of integers in
ascending order

Source Code:

#include <algorithm>
#include <iostream>
#include <iterator>

// Radix sort comparator for 32-bit two's complement integers

class radix_test
{
const int bit; // bit position [0..31] to examine
public:
radix_test(int offset) : bit(offset) {} // constructor

bool operator()(int value) const // function call operator

{
if (bit == 31) // sign bit
return value < 0; // negative int to left partition
else
return !(value & (1 << bit)); // 0 bit to left partition
}
};

// Least significant digit radix sort

void lsd_radix_sort(int *first, int *last)
{
for (int lsb = 0; lsb < 32; ++lsb) // least-significant-bit
{
std::stable_partition(first, last, radix_test(lsb));
}
}

// Most significant digit radix sort (recursive)

void msd_radix_sort(int *first, int *last, int msb = 31)
{

if (first != last && msb >= 0)

{
int *mid = std::partition(first, last, radix_test(msb));
msb--; // decrement most-significant-bit
msd_radix_sort(first, mid, msb); // sort left partition
msd_radix_sort(mid, last, msb); // sort right partition
}
}
65
Data Structures Using C++

// test radix_sort
int main()
{
int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };

lsd_radix_sort(data, data + 8);

// msd_radix_sort(data, data + 8);

std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

return 0;
}

Output:

-802 -90 2 24 45 66 75 170

Viva Questions:
1. What is meant by radix sort?
2. What is the best case time complexity of radix sort?
3. What is the average case time complexity of radix sort?
4. What is the worst case time complexity of radix sort?
5. Give the examples to radix sort?

66
Data Structures Using C++

11.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.

Source Code:

#include <iostream>
using namespace std;

// Node class
class Node {
int key;
Node* left;
Node* right;
public:
Node() { key=-1; left=NULL; right=NULL; };

void setKey(int aKey) { key = aKey; };

void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
}

// Tree class
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(int key);
void inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
void addNode(int key, Node* leaf);
void freeNode(Node* leaf);
}

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
67
Data Structures Using C++

Tree::~Tree() {
freeNode(root);
}
// Free the node
void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}

// Add a node
void Tree::addNode(int key) {
// No elements. Add the root
if ( root == NULL ) {
cout << "add root node ... " << key <<
endl; Node* n = new Node();
n->setKey(key);
root = n;
}
else {
cout << "add other node ... " << key << endl;
addNode(key, root);
}
}

// Add a node (private)

void Tree::addNode(int key, Node* leaf)
{ if ( key <= leaf->Key() ) {
if ( leaf->Left() != NULL )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
leaf->setLeft(n);
}
}
else {
if ( leaf->Right() != NULL )
addNode(key, leaf->Right());
else {
Node* n = new Node();
n->setKey(key);
leaf->setRight(n);
68
Data Structures Using C++

}
}
}

// Print the tree in-order

// Traverse the left sub-tree, root, right sub-tree
void Tree::inOrder(Node* n) {
if ( n ) {
inOrder(n->Left());
cout << n->Key() << " ";
inOrder(n->Right());
}
}

// Print the tree pre-order

// Traverse the root, left sub-tree, right sub-tree
void Tree::preOrder(Node* n) {
if ( n ) {
cout << n->Key() << " ";
preOrder(n->Left());
preOrder(n->Right());
}
}

// Print the tree post-order

// Traverse left sub-tree, right sub-tree, root
void Tree::postOrder(Node* n) {
if ( n ) {
postOrder(n->Left());
postOrder(n->Right());
cout << n->Key() << " ";
}
}

// Test main program

int main() {
Tree* tree = new Tree();
tree->addNode(30);
tree->addNode(10);
tree->addNode(20);
tree->addNode(40);
tree->addNode(50);
cout << "In order traversal" <<
endl; tree->inOrder(tree->Root());
cout << endl;
cout << "Pre order traversal" <<
endl; tree->preOrder(tree->Root());

69
Data Structures Using C++

cout << endl;

cout << "Post order traversal" <<

endl; tree->postOrder(tree->Root());
cout << endl;
delete tree;
return 0;
}

OUTPUT:-
add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
In order traversal
10 20 30 40 50
Pre order traversal
30 10 20 40 50
Post order traversal
20 10 50 40 30

70
Data Structures Using C++

12.Write a C++ program that uses functions to perform the following:

a) Create a binary search tree of integers.
b) Search for an integer key in the above binary search tree non recursively.
c) Search for an integer key in the above binary search tree recursively.

Algorithm:
Algorithm: Insert(root, ele)
{
if tree is empty then insert a node as root node otherwise go to next step
if ele is less than the root node the insert left sub tree of root node
otherwise insert right sub tree of root node
}

Algorithm: Search for the element

Here k is the key that is searched for and x is the start node.
BST -Search(x,k)
1:y<-x
2:whiley!=nil
do
3:if key[y] =k
Then return y
4:else if key[y]< k
then y <-right[y]
5:else y<- left [y]
6: return (“\NOT FOUND")

Source Code:

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;

void insert(int,int );
void display(int);
int search(int);
int search1(int,int);
int tree[40],t=1,s,x,i;

main()
{
int ch,y;
for(i=1;i<40;i++)
tree[i]=-1;
while(1)
{

71
Data Structures Using C++

cout <<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.SEARCH\n5.EXIT\nEnter your choice:";

cin >> ch;
switch(ch)
{
case 1:
cout <<"enter the element to insert";
cin >> ch;
insert(1,ch);
break;
case 2: display(1);
cout<<"\n";
for(int i=0;i<=32;i++)
cout <<i;
cout <<"\n";
break;
case 3:
cout <<"enter the element to search:";
cin >> x;
y=search(1);
if(y == -1) cout <<"no such element in
tree"; else cout <<x << "is in" <<y
<<"position"; break;
case 5:
exit(0);
}
}
}

void insert(int s,int ch )

{
int x;
if(t==1)
{
tree[t++]=ch;
return;
}
x=search1(s,ch);
if(tree[x]>ch)
tree[2*x]=ch;
else
tree[2*x+1]=ch;
t++;
}

int search(int s)
{

72
Data Structures Using C++

if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return tree[s];
if(tree[s]>x)
search(2*s);
else if(tree[s]<x)
search(2*s+1);
else
return s;
}

void display(int s)
{
if(t==1)
{cout <<"no element in tree:";
return;}
for(int i=1;i<40;i++)
if(tree[i]==-1)
cout <<" ";
else cout <<tree[i];
return ;
}

int search1(int s,int ch)

{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return s/2;
if(tree[s] > ch)
search1(2*s,ch);
else search1(2*s+1,ch);
}

OUTPUT
1. INSERT
2. DELETE
3. DISPLAY
4. SEARCH

73
Data Structures Using C++

5. EXIT
Enter your choice:3

no element in tree:
0123456789011121314151617181920212223242526272829303132

1. INSERT
2. DELETE
3. DISPLAY
4. SEARCH
5. EXIT
Enter your choice:1

Enter the element to insert 10

1.INSERT
2. DELETE
3. DISPLAY
4. SEARCH
5. EXIT
Enter your choice:4

Enter the element to search: 10

10 is in 1 position
1. INSERT
2. DELETE
3. DISPLAY
4. SEARCH
5. EXIT

Enter your choice:5

74
Data Structures Using C++

75
Data Structures Using C++

76
Data Structures Using C++

77
Data Structures Using C++

78
Data Structures Using C++

79
Data Structures Using C++

80
Data Structures Using C++

81