You will implement 3 recursive methods that operate on binary trees (any binary

Question

You will implement 3 recursive methods that operate on binary trees (any binary trees, not necessarily balanced, not necessarily BSTs). All methods take a reference to the root node.Implement a method that finds the number of nodes in the longest path in the given tree.int longestPath(Node root). As an example, for a full tree with 3 nodes this would return 2, but for a degenerate tree with 3 nodes looking like a linked list it would return 3. Implement a method that sets the data member of all the nodes in the tree to the size of the subtree rooted at that node. void setSize(Node root). As an example, for a full tree with 3 nodes this would set the data member of the root node to 3 and the data member of each child to 1. Implement a method that changes the tree as if it was flipped left to right. void flip(Node root). You will implement a method that reads in the given students file and counts how many times each first name occurs. It then prints in alphabetical order only the first names that occur "threshold" or more times and their occurrence count, one name-count per line. void printFrequentNames(String filename, int threshold). Write a program that maintains the names, addresses and phone numbers in an address book by using a hash table. Also, you should be able to enter, delete, modify (names, addresses and phone numbers), or search the data stored in hash table based on the name. A client

Explanation / Answer

#include<iostream>
using namespace std;

class HASHTABLE {
  
public:
//creating array that holds 27 elements
int hashTable[27];

//table size
int tableSize;

HASHTABLE() {
//table size
tableSize = 27;
  
//initializing hashtable to -1
for (int i = 0; i < tableSize; i++)
hashTable[i] = -1;

}

//defining Hash(int)

int Hash(int data) {
//returning data modulo(%) the tablesize
return (data % tableSize);
}

//add function hat takes an integer

bool add(int data) {
//calls above hash function
int key = Hash(data);

if (hashTable[key] == -1) {
//adds to table if collision is not found
hashTable[key] = data;

//returns true that the data is added
return true;
} else {
//linear probing adding to hash table
for (int i = key + 1; i < (key + tableSize); i++) {
//creates new key by linear probing
int newKey = i % tableSize;
if (hashTable[newKey] == -1) {
//adds to hashtable
hashTable[newKey] = data;

//returns true that the data is added
return true;
}
}
}

//returns false if data cannot be inserted. i.e. table is full
return false;
}

//lookup function

int lookup(int data) {
//gets key
int key = Hash(data);

//liner probing
for (int i = key; i < (key + tableSize); i++) {
//if data exists return true
if (hashTable[i] == data)
return 1;
}

//data not found, so -1
return -1;
}

};

int main() {

HASHTABLE ht = HASHTABLE();

//choice;
int choice;
//to store temp data : data
int data;
while (1) {
cout << " ";
cout << "Enter 1 to add ";
cout << "Enter 2 to lookup ";
cout << "And anyother number to exit ";

cout << "Enter choice: ";
cin>>choice;

switch (choice) {
case 1:
cout << " ";
cout << "Enter data to be added: ";
cin>>data;
if (ht.add(data)) {
cout << "Data added ";
} else
cout << "hash table full ";
break;

case 2:
cout << " ";
cout << "Enter lookup data: ";
cin>>data;
if (ht.lookup(data) == 1) //data found then
{
cout << "Yes.. it exists in hashtable !! ";
} else
cout << "No.. it does not exist in hashtable !! ";
break;

case 3: return 0;

default: return 0;
}
}

cout << " ";
return 0;
}

----------------------------------------------------------------------

OUTPUT

Enter 1 to add
Enter 2 to lookup
Enter 3 to exit
Enter choice: 1

Enter data to be added: 1
Data added

Enter 1 to add
Enter 2 to lookup
Enter 3 to exit
Enter choice: 1

Enter data to be added: 2
Data added

Enter 1 to add
Enter 2 to lookup
Enter 3 to exit
Enter choice: 2

Enter lookup data: 3
No.. it does not exist in hashtable !!

Enter 1 to add
Enter 2 to lookup
Enter 3 to exit
Enter choice: 2

Enter lookup data: 1
Yes.. it exists in hashtable !!

Enter 1 to add
Enter 2 to lookup
Enter 3 to exit
Enter choice: 3

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.