CSPL302 DATA STRUCTURE AND ALGORITHMS LAB

LTPC

0042

Course Pre-requisite:

• Basic knowledge in programming

Course Objective:

• To enable students write programs using various data structures, analyse and understand the
benefits of choosing the right data structure.

Course Outcomes:

• To write programs for search and sorting algorithms.

• To write programs for implementing stacks, queues and linked list.

• To write programs for searching using tree data structure.

• To write programs for identifying shortest path in a network.

• To write programs that implements hash tables.

LIST OF EXPERIMENTS

1. Searching Algorithms (With the Number of Key Comparisons) - Sequential, Binary and Fibonacci
Search Algorithms on an Ordered List

2. Sorting Algorithms: Insertion Sort, Selection Sort, Bubble Sort, Quick Sort, Heap Sort and Merge
Sort.

3. Implementation of Stack and Its Operations.

4. Application of Stack for Converting an Arithmetic Expression into Postfix Form and Evaluation of
Postfix Expression.

5. Implementation of Queue, Circular Queue, Priority Queue, Dequeue and Their Operations.

6. Implementation of Singly Linked List, Doubly Linked List, Circular Linked List.

7. Implementation of Binary Tree and Binary Traversal Techniques.

8. Implementation of Graph Traversal Techniques.

9. Implement Dijkstra’s Algorithm to Obtain the Shortest Paths.

10. Implementation of Hash Tables and its Operations.

1
Ex. No:1 Searching Algorithms (With the Number of Key Comparisons) - Sequential, Binary
Date: and Fibonacci Search Algorithms on an Ordered List

1a. Sequential Search:

Aim: To perform sequential search of an element on the given array.

Algorithm:

1. Start

2. Read number of array elements n

3. Read array elements Ai, i = 0,1,2,…n–1

4. Read search value

5. Assign 0 to found

6. Check each array element against search

7. If Ai = search then

found = 1

Print "Element found"

Print position i

Stop

8. If found = 0 then

print "Element not found"

Stop

Program

/* Linear search on a sorted array */

#include <stdio.h>

#include <conio.h>

main()

int a[50],i, n, val, found;

clrscr();

printf("Enter number of elements : ");

scanf("%d", &n);

printf("Enter Array Elements : \n");

2
for(i=0; i<n; i++)

scanf("%d", &a[i]);

printf("Enter element to locate : ");

scanf("%d", &val);

found = 0;

for(i=0; i<n; i++)

if (a[i] == val)

printf("Element found at position %d", i);

found = 1;

break;

if (found == 0)

printf("\n Element not found");

getch();

Output

Enter number of elements : 7

Enter Array Elements :

23 6 12 5 0 32 10

Enter element to locate : 5

Element found at position 3

Result

Thus an array was linearly searched for an element's existence.

3
1b.Binary Search

Aim: To locate an element in a sorted array using Binary search method

Algorithm

1. Start

2. Read number of array elements, say n

3. Create an array arr consisting n sorted elements

4. Get element, say key to be located

5. Assign 0 to lower and n to upper

6. While (lower < upper)

a. Determine middle element mid = (upper+lower)/2

b. If key = arr[mid] then

i. Print mid

ii. Stop

c. Else if key > arr[mid] then

i. lower = mid + 1

d. else

i. upper = mid – 1

7. Print "Element not found"

8. Stop

Program

/* Binary Search on a sorted array */

#include <stdio.h>

void main()

int a[50],i, n, upper, lower, mid, val, found, att=0;

printf("Enter array size : ");

scanf("%d", &n);

for(i=0; i<n; i++)

a[i] = 2 * i;

printf("\n Elements in Sorted Order \n");

for(i=0; i<n; i++)

4
printf("%4d", a[i]);

printf("\n Enter element to locate : ");

scanf("%d", &val);

upper = n;

lower = 0;

found = -1;

while (lower <= upper)

mid = (upper + lower)/2;

att++;

if (a[mid] == val)

printf("Found at index %d in %d attempts", mid, att);

found = 1;

break;

else if(a[mid] > val)

upper = mid - 1;

else

lower = mid + 1;

if (found == -1)

printf("Element not found");

Output

Enter array size : 10

Elements in Sorted Order

0 2 4 6 8 10 12 14 16 18

Enter element to locate : 16

Found at index 8 in 2 attempts

Result: Thus an element is located quickly using binary search method.

5
1c.Fibonacci Search

Aim: To write a program to find the Fibonacci search

Algorithm:

1. Input a sorted array A[i] with n numbers and target element which we want to search for.

2. Start by generating a series of Fibonacci numbers until you find a number that is greater

than or equal to the length of the array. F(k) >= n Example – if n = 10

Then, fibonacci sequence we have is 0, 1, 1, 2, 3, 5, 8, 13, because 13 >= 10.

3. If F(k) = 0, then stop and print the message as element not found.

4. Name a variable “offset” = -1

5. Check index i = min(offset + F(k-2), n-1)

6. Compare

If Target Element = A[i],

return i and stop the search

If Target Element > A[i],

k = k-1, offset = i,

repeat step 5 and 6.

If Target Element < A[i],

k = k-2, repeat step 5 and 6.

Program:

#include <stdio.h>

int min(int, int);

int fibonacci_search(int[], int, int);

int min(int a, int b){

return (a > b) ? b : a;

int fibonacci_search(int arr[], int n, int key){

int offset = -1;

int Fm2 = 0;

int Fm1 = 1;

int Fm = Fm2 + Fm1;

while (Fm < n) {

6
 Fm2 = Fm1;

Fm1 = Fm;

Fm = Fm2 + Fm1;

while (Fm > 1) {

int i = min(offset + Fm2, n - 1);

if (arr[i] < key) {

Fm = Fm1;

Fm1 = Fm2;

Fm2 = Fm - Fm1;

offset = i;

} else if (arr[i] > key) {

Fm = Fm2;

Fm1 = Fm1 - Fm2;

Fm2 = Fm - Fm1;

} else

return i;

if (Fm1 && arr[offset + 1] == key)

return offset + 1;

return -1;

int main(){

int i, n, key, pos;

int arr[10] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};

printf("Array elements are: ");

int len = sizeof(arr) / sizeof(arr[0]);

for(int j = 0; j<len; j++){

printf("%d ", arr[j]);

n = 10;

7
 key = 67;

printf("\nThe element to be searched: %d", key);

pos = fibonacci_search(arr, n, key);

if(pos >= 0)

printf("\nThe element is found at index %d", pos);

else

printf("\nUnsuccessful Search");

OUTPUT:

Array elements are: 6 11 19 24 33 54 67 81 94 99

The element to be searched: 67

The element is found at index 6

Result: Thus the above program was executed and verified

8
 Ex.No.2 Sorting Algorithms: Insertion Sort, Selection Sort, Bubble Sort, Quick Sort, Heap
Sort and Merge Sort.

2a. Insertion Sort

Aim:To sort an array of N numbers using Insertion sort.

Algorithm

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Outer index i varies from second element to last element

5. Inner index j is used to compare elements to left of outer index

6. Insert the element into the appropriate position.

7. Display the array elements after each pass

8. Display the sorted array elements.

9. Stop

Program

/* Insertion Sort */

void main()

int i, j, k, n, temp, a[20], p=0;

printf("Enter total elements: ");

scanf("%d",&n);

printf("Enter array elements: ");

for(i=0; i<n; i++)

scanf("%d", &a[i]);

for(i=1; i<n; i++)

temp = a[i];

j = i - 1;

while((temp<a[j]) && (j>=0))

a[j+1] = a[j];

9
j = j - 1;

a[j+1] = temp;

p++;

printf("\n After Pass %d: ", p);

for(k=0; k<n; k++)

printf(" %d", a[k]);

printf("\n Sorted List : ");

for(i=0; i<n; i++)

printf(" %d", a[i]);

Output

Enter total elements: 6

Enter array elements: 34 8 64 51 32 21

After Pass 1: 8 34 64 51 32 21

After Pass 2: 8 34 64 51 32 21

After Pass 3: 8 34 51 64 32 21

After Pass 4: 8 32 34 51 64 21

After Pass 5: 8 21 32 34 51 64

Sorted List : 8 21 32 34 51 64

Result: Thus array elements was sorted using insertion sort.

10
2b.Selection Sort

Aim: Arrange the list of numbers in ascending order using Selection Sort.

Algorithm:

function selection sort (array [], integer variable n)

declare integer variable position

declare index variables i, j

begin:

loop (i = 0, i < n-1, i = i +1)

begin:

position = i

loop(j = i + 1, j < n, j = j ++)

begin:

if(array[j] < array[position]) then

position = j

end if

end

swap(array[position], a[i])

end

end

Program

#include <stdio.h>

#include <conio.h>

void main()

int arr[50], num, i, j, pos, temp;

printf("Enter the number of elements in the array: ");

scanf("%d", &num);

printf("\nEnter the numbers: ");

for(i = 0; i < num; i++)

scanf("%d", &arr[i]);

11
}

for(i = 0;i < (num - 1); i++)

pos = i;

for(j = i + 1; j < num; j++)

if (arr[pos] > arr[j])

pos = j;

if(pos != i)

temp = arr[i];

arr[i] = arr[pos];

arr[pos] = temp;

printf("\nThe array sorted in ascending order is as follows.\n");

for(i = 0; i < num; i++)

printf("%d ", arr[i]);

getch();

Output:

Enter the number of element in the array: 5

Enter the number: 9 5 1 3 7

The array sorted in ascending order is as follows 1 3 5 7 9

12
2c.bubble Sort

Aim:To sort an array of N numbers using Bubble sort.

Algorithm

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Outer Index i varies from last element to first element

a. Index j varies from first element to i-1

i. Compare elements Aj and Aj+1

ii. If out-of-order then swap the elements

iii. Display array elements after each pass

iv. Display the final sorted list

5. Stop

Program

/* 11b - Bubble Sort */

#include <stdio.h>

main()

int n, t, i, j, k, a[20], p=0;

printf("Enter total numbers of elements: ");

scanf("%d", &n);

printf("Enter %d elements: ", n);

for(i=0; i<n; i++)

scanf("%d", &a[i]);

for(i=n-1; i>=0; i--)

for(j=0; j<i; j++)

if(a[j] > a[j+1])

t = a[j];

13
a[j] = a[j+1];

a[j+1] = t;

p++;

printf("\n After Pass %d : ", p);

for(k=0; k<n; k++)

printf("%d ", a[k]);

printf("\n Sorted List : ");

for(i=0; i<n; i++)

printf("%d ", a[i]);

Output

Enter total numbers of elements: 8

Enter 8 elements: 8 6 10 3 1 2 5 4

After Pass 1 : 6 8 3 1 2 5 4 10

After Pass 2 : 6 3 1 2 5 4 8 10

After Pass 3 : 3 1 2 5 4 6 8 10

After Pass 4 : 1 2 3 4 5 6 8 10

After Pass 5 : 1 2 3 4 5 6 8 10

After Pass 6 : 1 2 3 4 5 6 8 10

After Pass 7 : 1 2 3 4 5 6 8 10

Sorted List : 1 2 3 4 5 6 8 10

Result

Thus an array was sorted using bubble sort.

14
2d. Quick sort

Aim:To sort an array of N numbers using Quick sort.

Algorithm

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Select an pivot element x from Ai

5. Divide the array into 3 sequences: elements < x, x, elements > x

6. Recursively quick sort both sets (Ai < x and Ai > x)

7. Display the sorted array elements

8. Stop

Program

/* 11c - Quick Sort */

#include<stdio.h>

#include<conio.h>

void qsort(int arr[20], int fst, int last);

main()

int arr[30];

int i, size;

printf("Enter total no. of the elements : ");

scanf("%d", &size);

printf("Enter total %d elements : \n", size);

for(i=0; i<size; i++)

scanf("%d", &arr[i]);

qsort(arr,0,size-1);

printf("\n Quick sorted elements \n");

for(i=0; i<size; i++)

printf("%d\t", arr[i]);

getch();

15
void qsort(int arr[20], int fst, int last)

int i, j, pivot, tmp;

if(fst < last)

pivot = fst;

i = fst;

j = last;

while(i < j)

while(arr[i] <=arr[pivot] && i<last)

i++

while(arr[j]>arr[pivot])

j—

if(i<j)

tmp=arr[i];

arr[i]=arr[j]

arr[j]=tmp

tmp=arr[pivot];

arr[pivot]=arr[j];

arr[j]=tmp

qsort(arr,fst,j-1)

qsort(arr,j+1,last)

16
Output

Enter total no. of the elements : 8

Enter total 8 elements :

127

-1

04

-2

Quick sorted elements

-2 -1 0 1 2 3 4 7

Result

Thus the array was sorted using quick sort‟s divide and conquers method.

17
2e. Heap sort

Aim: Program to sort elements of array using Heap sort

Algorithm:

1. Build Max Heap: Create a max heap by visualizing all the elements of the array in a binary
tree. This process ensures that the largest element is at the root of the heap.
2. Repeat the following steps until the heap contains only one element:
i. Swap: Remove the root element and put it at the end of the array (nth position). Put
the last item of the tree (heap) in the vacant place.
ii. Remove: Reduce the size of the heap by 1.
iii. Heapify: Heapify the root element again so that we have the highest element at the
root.
3. Obtain Sorted Array: The sorted array is obtained by reversing the order of the elements in
the input array

Program:

#include <iostream>

using namespace std;

// A function to heapify the array.

void MaxHeapify(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;

// Break if parent value is already greater than child value.

if (temp > a[j])

break;

// Switching value with the parent node if temp < a[j].

else if (temp <= a[j])

a[j/2] = a[j];

j = 2*j;

18
}

a[j/2] = temp;

return;

void HeapSort(int a[], int n)

int i, temp;

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

// Storing maximum value at the end.

temp = a[i];

a[i] = a[1];

a[1] = temp;

// Building max heap of remaining element.

MaxHeapify(a, 1, i - 1);

void Build_MaxHeap(int a[], int n)

int i;

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

MaxHeapify(a, i, n);

int main()

int n, i;

cout<<"\nEnter the number of data element to be sorted: ";

cin>>n;

n++;

int arr[n];

19
for(i = 1; i < n; i++)

cout<<"Enter element "<<i<<": ";

cin>>arr[i];

// Building max heap.

Build_MaxHeap(arr, n-1);

HeapSort(arr, n-1);

// Printing the sorted data.

cout<<"\nSorted Data ";

for (i = 1; i < n; i++)

cout<<"->"<<arr[i];

return 0;

Expected Output:

Enter the number of data element to be sorted: 5

Enter element 1: 4

Enter element 2: 2

Enter element 3: 1

Enter element 4: 5

Enter element 5: 0

Sorted Data ->0->1->2->4->5

20
2f. Merge sort

Aim:To sort an array of N numbers using Merge sort.

Algorithm

1. Start

2. Read number of array elements n

3. Read array elements Ai

4. Divide the array into sub-arrays with a set of elements

5. Recursively sort the sub-arrays

6. Display both sorted sub-arrays

7. Merge the sorted sub-arrays onto a single sorted array.

8. Display the merge sorted array elements

9. Stop

Program

/* 11d – Merge sort */

#include <stdio.h>

#include <conio.h>

void merge(int [],int ,int ,int );

void part(int [],int ,int );

int size;

main()

int i, arr[30];

printf("Enter total no. of elements : ");

scanf("%d", &size);

printf("Enter array elements : ");

for(i=0; i<size; i++)

scanf("%d", &arr[i]);

part(arr, 0, size-1);

printf("\n Merge sorted list : ");

for(i=0; i<size; i++)

printf("%d ",arr[i]);

21
getch();

void part(int arr[], int min, int max)

int mid;

if(min < max)

mid = (min + max) / 2;

part(arr, min, mid);

part(arr, mid+1, max);

merge(arr, min, mid, max);

if (max-min == (size/2)-1)

printf("\n Half sorted list : ");

for(i=min; i<=max; i++)

printf("%d ", arr[i]);

void merge(int arr[],int min,int mid,int max)

int tmp[30];

int i, j, k, m;

j = min;

m = mid + 1;

for(i=min; j<=mid && m<=max; i++)

if(arr[j] <= arr[m])

tmp[i] = arr[j];

j++;

22
}

else

tmp[i] = arr[m];

m++;

if(j > mid)

for(k=m; k<=max; k++)

tmp[i] = arr[k];

i++;

else

for(k=j; k<=mid; k++)

tmp[i] = arr[k];

i++;

for(k=min; k<=max; k++)

arr[k] = tmp[k];

Output

Enter total no. of elements : 8

Enter array elements : 24 13 26 1 2 27 38 15

Half sorted list : 1 13 24 26

Half sorted list : 2 15 27 38

23
Merge sorted list : 1 2 13 15 24 26 27 38

Result

Thus array elements was sorted using merge sort's divide and conquer method.

24
Ex.No.3 Implementation of Stack and Its Operations.

Date:

STACK USING ARRAY IMPLEMENTATION

Aim: To write a program for stack using array implementation.

Algorithm :

Step1:Define a array which stores stack elements..

Step 2: The operations on the stack are

a)PUSH data into the stack

b)POP data out of stack

Step 3: PUSH DATA INTO STACK

3a.Enter the data to be inserted into stack.

3b.If TOP is NULL

the input data is the first node in stack.

the link of the node is NULL.

TOP points to that node.

3c.If TOP is NOT NULL

the link of TOP points to the new node.

TOP points to that node.

Step 4: POP DATA FROM STACK

4a.If TOP is NULL

the stack is empty

4b.If TOP is NOT NULL

the link of TOP is the current TOP.

the pervious TOP is popped from stack.

Step 5. The stack represented by linked list is traversed to display its content.

PROGRAM:

#include<stdio.h>

#include<conio.h>

#define SIZE 5

int stack[SIZE],top=-1;

void push();

25
void pop();

void display();

void main()

int choice;

int isempty();

int length();

clrscr();

while(1)

printf(“\n 1.Push”);

printf(“\n 2. POP”);

printf(“\n 3.Display”);

printf(“\n 4. Length ”);

printf(“\n 5.Quit”);

printf(“\n Enter the choice:”);

scanf(“\n %d”,&choice);

switch(choice)

case 1: push();

break;

case 2: pop();

break;

case 3: display();

break;

case 4: printf(“\n No. of elements in the stack is %d”,length());

break;

case 5: exit(0);

break;

default: printf(“\n Invalid choice”);

26
 }

void push()

int n;

if(top==SIZE-1)

printf(“\n Stack is full”);

else

printf(“\nEnter the no.”);

scanf(“%d”,&n);

top++;

stack[top]=n;

void pop()

int n;

if(isempty())

printf(“\nStack is empty”);

top=-1;

else

n=stack[top];

printf(“\n %d is popped from the stack \n”,n);

--top;

27
}

void display()

int i,temp=top;

if(isempty())

printf(“\n Stack Empty”);

return;

printf(“\n Elements in the stack:”);

for(i=temp;i>=0;i--)

printf(“%d \n”,stack[i]);

int isempty()

return (top==-1);

int length()

return (top+1);

Output:

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 1

Enter the no. 10

28
1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 1

Enter the no. 20

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 1

Enter the no. 30

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 1

Enter the no. 40

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 3

Elements in the stack:

40

30

20

29
10

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 2

40 is popped from the stack

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 4

Number of elements in the stack is 3

1.Push

2. POP

3.Display

4. Length

5.Quit

Enter the choice: 5

Result: Thus the above program was executed successfully and verified.

30
Ex.no: 4

4a.

Aim: To convert infix expression to its postfix form using stack operations.

Algorithm

1. Start

2. Define a array stack of size max = 20

3. Initialize top = -1

4. Read the infix expression character-by-character

5. If character is an operand print it

6. If character is an operator

7. Compare the operator‟s priority with the stack[top] operator.

8. If the stack [top] operator has higher or equal priority than the inputoperator,

Pop it from the stack and print it.

9. Else

10. Push the input operator onto the stack

11. If character is a left parenthesis, then push it onto the stack.

12. If the character is a right parenthesis, pop all the operators from the stack andprint it

until a left parenthesis is encountered. Do not print the parenthesis.

Program

/* 4b - Conversion of infix to postfix expression */

#include <stdio.h>

#include <conio.h>

#include <string.h>

#define MAX 20

int top = -1;

char stack[MAX];

char pop();

void push(char item);

int prcd(char symbol)

31
switch(symbol)

case '+':

case '-':

return 2;

break;

case '*':

case '/':

return 4;

break;

case '^':

case '$':

return 6;

break;

case '(':

case ')':

case '#':

return 1;

break;

int isoperator(char symbol)

switch(symbol)

case '+':

case '-':

case '*':

case '/':

case '^':

case '$':

32
case '(':

case ')':

return 1;

break;

default:

return 0;

void convertip(char infix[],char postfix[])

int i,symbol,j = 0;

stack[++top] = '#';

for(i=0;i<strlen(infix);i++)

symbol = infix[i];

if(isoperator(symbol) == 0)

else

postfix[j] = symbol;

j++;

if(symbol == '(')

push(symbol);

else if(symbol == ')')

while(stack[top] != '(')

postfix[j] = pop();

j++;

33
pop(); //pop out (.

Else

if(prcd(symbol) > prcd(stack[top]))

push(symbol);

else

while(prcd(symbol) <= prcd(stack[top]))

postfix[j] = pop();

j++;

push(symbol);

while(stack[top] != '#')

postfix[j] = pop();

j++;

postfix[j] = '\0';

main()

char infix[20],postfix[20];

clrscr();

printf("Enter the valid infix string: ");

gets(infix);

34
convertip(infix, postfix);

printf("The corresponding postfix string is: ");

puts(postfix);

getch();

void push(char item)

top++;

stack[top] = item;

char pop()

char a;

a = stack[top];

top--;

return a;

Output

Enter the valid infix string: (a+b*c)/(d$e)

The corresponding postfix string is: abc*+de$/

Enter the valid infix string: a*b+c*d/e

The corresponding postfix string is: ab*cd*e/+

Enter the valid infix string: a+b*c+(d*e+f)*g

The corresponding postfix string is: abc*+de*f+g*+

Result: Thus the given infix expression was converted into postfix form using stack

35
4b.

Aim: To evaluate the given postfix expression using stack operations.

Algorithm

1. Start

2. Define a array stack of size max = 20

3. Initialize top = -1

4. Read the postfix expression character-by-character

5. If character is an operand push it onto the stack

6. If character is an operator

7. Pop topmost two elements from stack.

8. Apply operator on the elements and push the result onto the stack,

Eventually only result will be in the stack at end of the expression.

9. Pop the result and print it.

Program

/* Evaluation of Postfix expression using stack */

#include <stdio.h>

#include <conio.h>

struct stack

}s;

main()

int top;

float a[50];

char pf[50];

float d1,d2,d3;

int i;

clrscr();

s.top = -1;

printf("\n\n Enter the postfix expression: ");

gets(pf);

36
for(i=0; pf[i]!='\0'; i++)

switch(pf[i])

case '0':

case '1':

case '2':

case '3':

case '4':

case '5':

case '6':

case '7':

case '8':

case '9':

s.a[++s.top] = pf[i]-'0';

break;

case '+':

d1 = s.a[s.top--];

d2 = s.a[s.top--];

s.a[++s.top] = d1 + d2;

break;

case '-':

d2 = s.a[s.top--];

d1 = s.a[s.top--];

s.a[++s.top] = d1 - d2;

break;

case '*':

d2 = s.a[s.top--];

d1 = s.a[s.top--];

s.a[++s.top] = d1*d2;

break;

37
case '/':

d2 = s.a[s.top--];

d1 = s.a[s.top--];

s.a[++s.top] = d1 / d2;

break;

printf("\n Expression value is %5.2f", s.a[s.top]);

getch();

Output

Enter the postfix expression: 6523+8*+3+*

Expression value is 288.00

Result: Thus the given postfix expression was evaluated using stack.

38
Ex.No: 7

Aim: Implementation of BinaryTree and Binary Tree Traversal techniques (in order, pre

order, post order, level-order)

Description :

Trees: A tree is a nonlinear hierarchical data structure that consists of nodes connected by

edges.

Node : A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a

link/pointer to child nodes.The node having at least a child node is called an internal node.

Edge :It is the link between any two nodes.

Nodes and edges of a tree

Root:It is the topmost node of a tree.

Height of a Node :The height of a node is the number of edges from the node to the deepest

leaf (ie. the longest path from the node to a leaf node).

Depth of a Node :The depth of a node is the number of edges from the root to the node.

Height of a Tree:The height of a Tree is the height of the root node or the depth of the

deepest node.

A) Binary Tree

Aim :Program to create a Binary tree and perform inorder,preorder,postorder

traversal on the tree.

#include<stdio.h>

#include<stdlib.h>

typedef char EleType;

typedef struct BiTNode{

EleType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//Create a binary tree recursively according to the pre-order traversal method

bool createBitTree(BiTree *T){

EleType data;

39
scanf("%c",&data);

if('#' == data)

*T = nullptr;

else{

(*T) = (BiTree)malloc(sizeof(BiTNode));

if(!(*T)){

exit(-1);

(*T)->data = data;

createBitTree(&(*T)->lchild);//Create the left subtree

createBitTree(&(*T)->rchild);//Create the right subtree

return true;

void visite(EleType data){

printf("%c",data);

//Recursively realize the first order traversal of the binary tree

bool proOrderTraverse(BiTree &T){

if(T == nullptr)

return false;

visite(T->data);

proOrderTraverse(T->lchild);

proOrderTraverse(T->rchild);

return true;

//Recursively implement in-order traversal of the binary tree

bool inOrderTraverse(BiTree &T){

if(T == nullptr)

return false;

inOrderTraverse(T->lchild);

40
visite(T->data);

inOrderTraverse(T->rchild);

return true;

//Recursively implement post-order traversal of the binary tree

bool postOrderTraverse(BiTree &T){

if(T == nullptr)

return false;

postOrderTraverse(T->lchild);

postOrderTraverse(T->rchild );

visite(T->data);

return true;

int main(){

BiTree T;

createBitTree(&T);

proOrderTraverse(T);

printf("\n");

inOrderTraverse(T);

printf("\n");

postOrderTraverse(T);

getchar();

return 0;

Expected Output:

ABC##DE#G##F###

ABCDEGF

CBEGDFA

CGEFDBA

41
Ex.No: 8

Aim To implement breadth first graph traversal.

Algorithm

Program

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 5

struct Vertex {

char label;

bool visited;

};

//queue variables

int queue[MAX];

int rear = -1;

int front = 0;

int queueItemCount = 0;

//graph variables

//array of vertices

struct Vertex* lstVertices[MAX];

//adjacency matrix

int adjMatrix[MAX][MAX];

//vertex count

int vertexCount = 0;

//queue functions

void insert(int data) {

queue[++rear] = data;

queueItemCount++;

int removeData() {

42
queueItemCount--;

return queue[front++];

bool isQueueEmpty() {

return queueItemCount == 0;

//graph functions

//add vertex to the vertex list

void addVertex(char label) {

struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));

vertex->label = label;

vertex->visited = false;

lstVertices[vertexCount++] = vertex;

//add edge to edge array

void addEdge(int start,int end) {

adjMatrix[start][end] = 1;

adjMatrix[end][start] = 1;

//display the vertex

void displayVertex(int vertexIndex) {

printf("%c ",lstVertices[vertexIndex]->label);

//get the adjacent unvisited vertex

int getAdjUnvisitedVertex(int vertexIndex) {

int i;

for(i = 0; i<vertexCount; i++) {

if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)

return i;

return -1;

43
}

void breadthFirstSearch() {

int i;

//mark first node as visited

lstVertices[0]->visited = true;

//display the vertex

displayVertex(0);

//insert vertex index in queue

insert(0);

int unvisitedVertex;

while(!isQueueEmpty()) {

//get the unvisited vertex of vertex which is at front of the queue

int tempVertex = removeData();

//no adjacent vertex found

while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {

lstVertices[unvisitedVertex]->visited = true;

displayVertex(unvisitedVertex);

insert(unvisitedVertex);

//queue is empty, search is complete, reset the visited flag

for(i = 0;i<vertexCount;i++) {

lstVertices[i]->visited = false;

int main() {

int i, j;

for(i = 0; i<MAX; i++) // set adjacency {

for(j = 0; j<MAX; j++) // matrix to 0

adjMatrix[i][j] = 0;

44
addVertex('S'); // 0

addVertex('A'); // 1

addVertex('B'); // 2

addVertex('C'); // 3

addVertex('D'); // 4

addEdge(0, 1); // S – A

addEdge(0, 2); // S - B

addEdge(0, 3); // S - C

addEdge(1, 4); // A - D

addEdge(2, 4); // B - D

addEdge(3, 4); // C - D

printf("\nBreadth First Search: ");

breadthFirstSearch();

return 0;

Output

Breadth First Search: S A B C D

Result : Thus the graph using breadth first search traversal was demonstrated.

45
Aim To implement Depth first graph traversal.

Algorithm

Program

#include<stdio.h>

void DFS(int);

int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10]

void main()

int i,j;

printf("Enter number of vertices:");

scanf("%d",&n);

//read the adjecency matrix

printf("\nEnter adjecency matrix of the graph:");

for(i=0;i<n;i++)

for(j=0;j<n;j++)

scanf("%d",&G[i][j]);

DFS-iterative (G, s):

let S be stack

S.push( s )

mark s as visited.

//Where G is graph and s is source vertex

//Inserting s in stack

while ( S is not empty):

//Pop a vertex from stack to visit next

v = S.top( )

S.pop( )

//Push all the neighbours of v in stack that are not visited

for all neighbours w of v in Graph G:

if w is not visited :

S.push( w )

mark w as visited

46
DFS-recursive(G, s):

mark s as visited

for all neighbours w of s i

//visited is initialized to zero

for(i=0;i <n;i++)

visited[i]=0

DFS(0);

Void DSF(int i)

Int j;

Printf(“%d”,i)

Visited[i]=1;

For(j=0;j<n;j++)

If(!visited[j]&&g[i][j]==1)

DFS(j);

Output:

47
Result : Thus the graph using depth first search traversal was demonstrated.

STACK USING LINKED LIST

Aim:

To write a program for stack using linked list implementation.

Algorithm :

Step1:Define a C-struct for each node in the stack. Each node in the stack

contains data and link to the next node. TOP pointer points to last

node inserted in the stack.

Step 2: The operations on the stack are

a)PUSH data into the stack

b)POP data out of stack

Step 3: PUSH DATA INTO STACK

3a.Enter the data to be inserted into stack.

3b.If TOP is NULL

the input data is the first node in stack.

the link of the node is NULL.

TOP points to that node.

3c.If TOP is NOT NULL

the link of TOP points to the new node.

TOP points to that node.

48
 Step 4: POP DATA FROM STACK

4a.If TOP is NULL

the stack is empty

4b.If TOP is NOT NULL

the link of TOP is the current TOP.

the pervious TOP is popped from stack.

Step 5. The stack represented by linked list is traversed to display its content.

PROGRAM:

# include<stdio.h>

# include<conio.h>

struct node

int info;

struct node *link;

} *top=NULL;

main()

49
{

int choice;

while(1)

{ printf("1.Push\n");

printf("2.Pop\n");

printf("3.Display\n");

printf("4.Quit\n");

printf("Enter your choice : ") ;

scanf("%d", &choice);

switch(choice)

case 1:

push();

break;

case 2:

pop();

break;

case 3:

display();

break;

case 4:

exit(1);

default :

printf("Wrong choice\n");

}/*End of switch */

}/*End of while */

}/*End of main() */

push()

50
struct node *tmp;

int pushed_item;

tmp = (struct node *)malloc(sizeof(struct node));

printf("Input the new value to be pushed on the stack : ");

scanf("%d",&pushed_item);

tmp->info=pushed_item;

tmp->link=top;

top=tmp;

}/*End of push()*/

pop()

struct node *tmp;

if(top == NULL)

printf("Stack is empty\n");

else

{ tmp=top;

printf("Popped item is %d\n",tmp->info);

top=top->link;

free(tmp);

}/*End of pop()*/

display()

{ struct node *ptr;

ptr=top;

if(top==NULL)

printf("Stack is empty\n");

else

51
printf("Stack elements :\n");

while(ptr!= NULL)

printf("%d\n",ptr->info);

ptr = ptr->link;

}/*End of while */

}/*End of else*/

}/*End of display()*/

Output:

1.Push

2. POP

3.Display

5.Quit

Enter the choice: 1

Input the new value to be pushed on the stack :. 10

52
1.Push

2. POP

3.Display

5.Quit

Enter the choice: 1

Input the new value to be pushed on the stack : 20

1.Push

2. POP

3.Display

5.Quit

Enter the choice: 1

Input the new value to be pushed on the stack : 30

1.Push

2. POP

3.Display

5.Quit

Enter the choice: 1

Input the new value to be pushed on the stack : 40

1.Push

2. POP

3.Display

5.Quit

53
Enter the choice: 3

Elements in the stack:

40

30

20

10

1.Push

2. POP

3.Display

5.Quit

Enter the choice: 2

40 is popped from the stack

1.Push

2. POP

3.Display

5.Quit

Enter the choice: 5

54