Question

1. In Lab 4, you developed a program to build a Max Heap, and then Heap Sort. Update the program by adding two additional functions: (a) AddData(A, N, V) where V is the new value added. (b) Delete a data Delete by giving the index of the data position Make sure to display the array after calling each of the function. 2. Write a program to implement Binary Search Algorithm, which will return the index of the data searched (V). The function will take the array A, size of array, N and a search key V as inputs and will return the data position number. If the data is not found, it will return -1. Call this function from main, and try searching for various data. 3. Given the following data: 1,4,7,12, 20, 34, 56, 60, 71, 82, 90, 111, 124, 156 Illustrate how will you search for the following values, and how many searches will be required for each of them, when you use Binary Search Algorithm. a) V = 200 b) V = 12 c) V = 90 4. a) Construct a Binary Search Tree using the following data: 45, 34, 12, 67, 50, 30, 8, 61, 24 b) Now illustrate how you will find out 24 from the tree, and how many searches will be needed. c) Give the inorder, preorder and post order tree traversal sequences. d) Illustrate how you will delete the root, and reconstruct the binary search tree. 5. A C++ program is kept in blackboard to implement Binary Search Tree. You are required to run that by adding at least 10 random data, then display the tree and draw in a piece of paper. There is a function kept in this program which is not utilized. Try calling this function suitably to search for a data. The program is called Binary Search Tree.cpp

Answer 1

1)

#include <iostream>

using namespace std;

// Function to create max heap

void MaxHeap(int numbers[], int pos, int size)

{

// Stores the current position data

int temp = numbers[pos];

// Calculates the next child position

int nextPos = 2 * pos;

// Loops till next position is less than or equals to size of the number array

while (nextPos <= size)

{

// Checks if next position is less than size and

// data at next position plus one position is greater than the next position data

if (nextPos < size && numbers[nextPos + 1] > numbers[nextPos])

// Update the next position

nextPos = nextPos + 1;

// Stop the loop if parent value is already greater than child value

if (temp > numbers[nextPos])

break;

// Switching value with the parent node id it is less

else if (temp <= numbers[nextPos])

{

numbers[nextPos / 2] = numbers[nextPos];

nextPos = 2 * nextPos;

}// End of else

}// End of while loop

numbers[nextPos / 2] = temp;

return;

}// End of function

// Function to perform heap sort

void HeapSortImplementation(int numbers[], int size)

{

// Loops from end of the array to 2nd position in reverse order

for (int pos = size; pos >= 2; pos--)

{

// Storing maximum value at the end

// Using swapping process

int temp = numbers[pos];

numbers[pos] = numbers[1];

numbers[1] = temp;

// Calls the function to build max heap of remaining element

MaxHeap(numbers, 1, pos - 1);

}// End of for loop

}// End of function

// Function to call the function maxHeap to generate max heap

void BuildMaximumHeap(int numbers[], int size)

{

for(int pos = size / 2; pos >= 1; pos--)

MaxHeap(numbers, pos, size);

}// End of function

// main function definition

int main()

{

int size;

// Accepts the size of the array

cout<<"\n Enter the number of element to be sorted: ";

cin>>size;

size++;

// Creates an array

int numbers[size];

// Loops till size

for(int c = 1; c < size; c++)

{

// Accepts each element

cout<<"Enter element "<<c<<": ";

cin>>numbers[c];

}// End of for loop

// Calls the function to build max heap

BuildMaximumHeap(numbers, size - 1);

// Calls the function to sort

HeapSortImplementation(numbers, size - 1);

cout<<"\nSorted Data ";

// Loops till end to print the sorted data.

for (int c = 1; c < size; c++)

cout<<"->"<<numbers[c];

return 0;

}// End of main function

Sample Output:

Enter the number of element to be sorted: 8

Enter element 1: 10

Enter element 2: 222

Enter element 3: 89

Enter element 4: 3

Enter element 5: 701

Enter element 6: 33

Enter element 7: 56

Enter element 8: 98

Sorted Data ->3->10->33->56->89->98->222->701

2)

#include <iostream>

#include <time.h>

#include <stdlib.h>

using namespace std;

// Function to display the data set

void display(int *list, int size)

{

// Loops till end of the data set

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

// Displays each element data

cout << list[i] << " ";

cout << endl;

}// End of function

// Function to search a key in the list using binary search

// Returns found index position if found otherwise returns -1

int binarySearch(int *list, int size, int key)

{

// Initializes the beginning index position of the list to zero

int begin = 0;

// Initializes the last index position of the list to size minus one

int end = size - 1;

// Loops till beginning is less than or equals to end

while (begin <= end)

{

// Calculates the middle index position

int middle = (begin + end) / 2;

// Checks if the middle index position value is equals to key value

if (list[middle] == key)

// Returns the found index position as middle value

return middle;

// Otherwise checks if key value is less than the middle index position value of the list

else if (key < list[middle])

// Update the end index position by middle minus one

end = middle - 1;

// Otherwise the key value is greater than the middle index position value of the list

else

// Update the beginning index position by middle plus one

begin = middle + 1;

}// End of while loop

// Returns -1 for not found

return -1;

}// End of while loop

// main function definition

int main()

{

// Defines a constant for list size to 1000

const int SIZE = 100;

// Defines a constant for number of searches to 20

const int NUM_SEARCHES = 5;

// Declares an array of size 1000

int list[SIZE];

// Declares an array of size 20 to store search numbers

int testValues[NUM_SEARCHES];

srand(time(0));

// Loops till end of the list size

for (int i = 0; i < SIZE; i++)

// Generates random number and stores it in array

list[i] = rand() % (SIZE);

// Loops till end of the searched array size

for (int i = 0; i < NUM_SEARCHES; i++)

// Generates random number and stores it in array

testValues[i] = rand() % (SIZE * 5);

// Calls the function to display the numbers

cout<<"\n *********** Numbers in the list *********** \n";

display(list, SIZE);

// Calls the function to display the numbers to search

cout<<"\n *********** Numbers to search *********** \n";

display(list, NUM_SEARCHES);

cout << "\n *********** BINARY SEARCH TEST *********** \n";

// Loops till end of the search array size

for (int i = 0; i < NUM_SEARCHES; i++)

{

// Calls the function to perform binary search and store the found index status

int index = binarySearch(list, SIZE, testValues[i]);

// Checks if found index position is -1 then display message key not found with search key value

if (index == -1)

cout << "Did not find " << testValues[i] << endl;

// Otherwise, display the search key with found index position

else

cout << "Found " << testValues[i] << " at index " << index << endl;

}// End of for loop

}// End of main function

Sample Output:

*********** Numbers in the list ***********

17 20 16 54 15 86 45 40 47 6 54 5 3 88 33 16 18 20 35 39 40 62 39 68 32 98 60 78 65 34 79 11 58 57 69 5 63 36 43 95 79 14 47 6 3 86 29 80 63 47 78 55 87 67 33 29 37 5 74 86 34 3 64 18 73 65 54 97 59 26 70 21 39 27 29 87 22 5 5 0 91 2 35 77 51 80 79 64 55 33 58 13 60 18 24 10 88 35 78 75

*********** Numbers to search ***********

17 20 16 54 15

*********** BINARY SEARCH TEST ***********

Did not find 231

Did not find 63

Did not find 94

Found 64 at index 87

Did not find 233

3) V = 200

1,4,7,12,20,34,56,60,71,82,90,111,124,156 In the above array length is 14, so, middle position is 6 and value stored at middle position is 56. Searching element is greater than the middle position value so, begin index is shifted to middle plus one so, new middle position is 10th position. 10th position contains value 90, searching element 200 is greater than the middle position value so begin index is shifted to middle plus one and new middle position is 12. 12th index position contains 124 which is less then the searching element so, new middle position is 13, which is 156 and stops the loop because while (begin <= end) condition is false. So, it requires 4 search process.
v = 12

1,4,7,12,20,34,56,60,71,82,90,111,124,156 In the above array length is 14, so, middle position is 6 and value stored at middle position is 56. Searching element 12 is less than the middle position value so, end index is shifted to middle minus one so, new middle position is 2nd position. 2nd position contains value 7, searching element 12 is greater than the middle position value so begin index is shifted to middle plus one and new middle position is 4. 4th index position contains 20 which is greater then the searching element so, new middle position is 3, which is 12 which is matching with the searching element. So, it requires 4 search process.
v = 90

1,4,7,12,20,34,56,60,71,82,90,111,124,156 In the above array length is 14, so, middle position is 6 and value stored at middle position is 56. Searching element 90 is greater than the middle position value so, begin index is shifted to middle plus one so, new middle position is 10th position. 10th index position value is 90 which, is matching with the searching element. So, it requires 2 search process.