Binary Trees
$30-250 USD
Paid on delivery
4. Write a program to find the number of comparisons sing the binary search and sequential search algorithms as follows:
a) Use a random number generator to fill list.
b) Use any sorting algorithm to sort list. Alternatively, you can use the function insertOrd to initially insert all the elements in the list.
c) Search the list for some items, as follows:
1. Use the binary search algorithm to search the list. (You might need to modify the algorithm given in this chapter to count the number of comparisons)
2. Use the binary search algorithm to search the list, switching to a sequential search when the size of the search list reduces to less than 15. (Use the sequential search algorithm for a sorted list).
d) Print the number of comparisons for steps c 1 and c 2. If the item is found in the list, then print its position.
14. In the Programming Exercise Election Results, the class candidatedateType contains the function calculateTotalVotes. After processing the voting data, this function calculates the total number of votes received by a candidate. The function updateVotesByRegion (of the class candidateType) updates only the number of votes for a particular region. Modify the definition of this function so that it also updates the total number of votes received by the candidate. By doing so, the function addVotes in the main program is no longer needed. Modify and run your program with the modified definition of the function updateVotesByRegion.
Will submit attachment for exercise 14.
14. (Video Store Program) In Exercise 14 in Chapter 5, you were asked to design and implement a class to maintain customer data in a linked list. Because the search on a linked list is sequential and, therefore, can be time consuming, design and implement the class customerBTreeType so that this customer data can be stored in a binary search tree. The class customerBTreeType must be derived from the class bSearchTreeType as designed in this chapter.
2. Write a program that outputs the nodes of a graph in a breadth-first traversal.
#include <stdio.h>
typedef struct node {
int value;
struct node *right;
struct node *left;
} mynode;
mynode *root;
add_node(int value);
void levelOrderTraversal(mynode *root);
int main(int argc, char* argv[]) {
root = NULL;
add_node(5);
add_node(1);
add_node(-20);
add_node(100);
add_node(23);
add_node(67);
add_node(13);
printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
levelOrderTraversal(root);
getch();
}
// Function to add a new node...
add_node(int value) {
mynode *prev, *cur, *temp;
temp = malloc(sizeof(mynode));
temp->value = value;
temp->right = NULL;
temp->left = NULL;
if(root == NULL) {
printf("\nCreating the root..\n");
root = temp;
return;
}
prev = NULL;
cur = root;
while(cur != NULL) {
prev = cur;
//cur = (value < cur->value) ? cur->left:cur->right;
if(value < cur->value) {
cur = cur->left;
} else {
cur = cur->right;
}
}
if(value < prev->value) {
prev->left = temp;
} else {
prev->right = temp;
}
}
// Level order traversal..
void levelOrderTraversal(mynode *root) {
mynode *queue[100] = {(mynode *)0}; // Important to initialize!
int size = 0;
int queue_pointer = 0;
while(root) {
printf("[%d] ", root->value);
if(root->left) {
queue[size++] = root->left;
}
if(root->right) {
queue[size++] = root->right;
}
root = queue[queue_pointer++];
}
}
6. Write a program to test the breadth-first topological ordering algorithm.
8. Write a program to implement Fleury’s algorithm as described in this chapter.
10. Redo Programming Exercise 14 of Chapter 5 so that it uses the STL class set to process the list of videos rented by the customer and the list of store members.
Project ID: #788682