Question: How do I modify the code below to search for integers from a txt file to see if they are already in the tree? I
How do I modify the code below to search for integers from a txt file to see if they are already in the tree? I would also like to report how many comparisons the program had to make in order to search for these integers. The code is below in C++
#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct BST{
int data;
struct BST *left, *right;
} node;
class Binary_Tree{
public:
void insert(node *root, node *new_node){
if (new_node->data < root->data){
if (root->left == NULL)
root->left = new_node;
else
insert(root->left, new_node);
}
if (new_node->data > root->data){
if (root->right == NULL)
root->right = new_node;
else
insert(root->right, new_node);
}
}
public:
node *search(node *root, int key, node **parent){
node *temp;
temp = root;
while (temp != NULL){
if (temp->data == key){
cout<<" The Element "< return temp; } *parent = temp; if (temp->data > key) temp = temp->left; else temp = temp->right; } return NULL; } public: void inorder(node *temp){ if (temp != NULL){ inorder(temp->left); cout<<"\t"< inorder(temp->right); } } public: node *get_node(){ node *temp; temp = (node *) malloc(sizeof(node)); temp->left = NULL; temp->right = NULL; return temp; } public: node *delete_node(node *root, int key){ if(root == NULL) return root; if (key < root -> data){ root->left = delete_node(root->left, key); } else if(key > root -> data){ root->right = delete_node(root->right, key); } else{ if(root->left == NULL){ node *temp = root ->right; delete(root); return (temp); } else if(root -> right == NULL){ node *temp = root -> left; delete(root); return temp; } node *temp = minfind(root->right); root -> data = temp->data; root ->right = delete_node(root->right, temp->data); } return root; } node *minfind(node *P){ node *current = P; while(current->left !=NULL){ current = current->left; } return current; } }; int main(){ int nums[160] = {7711, 6837, 2525, 5542, 230, 1674, 4456, 2742, 5492, 7456, 6626, 1998, 3139, 6167, 4371, 6540, 3420, 1068, 8863, 6438, 3429, 9465, 6147, 7448, 8781, 4959, 5797, 8730, 1883, 7676, 5751, 7481, 2979, 2759, 2278, 7200, 6876, 1916, 1701, 4467, 7730, 4154, 8826, 8495, 5765, 8701, 1894, 8450, 6157, 1419, 9909, 8512, 8848, 7141, 1197, 9604, 2512, 4328, 5373, 1150, 6500, 9624, 6202, 9642, 7172, 9625, 8344, 7655, 6199, 2946, 8144, 8227, 1573, 3627, 6875, 1275, 7355, 4870, 6713, 6684, 5696, 9814, 7867, 4839, 6296, 5122, 7378, 6176, 4146, 9877, 1565, 5054, 5605, 9464, 7271, 9756, 8268, 2947, 3044, 4106, 8089, 5876, 8077, 5616, 5397, 5811, 6688, 5097, 8402, 5457, 2583, 1789, 6357, 5271, 3411, 2536, 5244, 6853, 1326, 8597, 7529, 2714, 9728, 3717, 3509, 6593, 2293, 6366, 6960, 2886, 8608, 4274, 9268, 2497, 1631, 6638, 7557, 6517, 1257, 9924, 9365, 3030, 3760, 4841, 7669, 4646, 7367, 8757, 1108, 2884, 9486, 3926, 7775, 6860, 6996, 5330, 8655, 8036, 4176, 6221}; Binary_Tree obj; int option; //char ans = 'N'; int key; node *new_node, *root, *tmp, *parent; node *get_node(); root = NULL; int count = 0; int i = 0; while (count < 160){ new_node = obj.get_node(); new_node->data = nums[count]; if (root == NULL) root = new_node; else obj.insert(root, new_node); cout << "*****" << (long)nums[count] << " "; count++; i++; } //input from number file ifstream inputFile; string line, n1; int num; inputFile.open("nums.txt"); if (!inputFile.fail()){ getline(inputFile, line); istringstream ss(line); while (getline(ss, n1, ',')){ num = stoi(n1); new_node = obj.get_node(); new_node->data = num; if (root == NULL) root = new_node; else obj.insert(root, new_node); cout << "num: " << num << endl; } } //Binary_Tree obj; //int option; char ans = 'N'; //int key; //node *new_node, *root, *tmp, *parent; //node *get_node(); //root = NULL; cout<<"------------------------------------------- "< cout<<" **** Program For Binary Search Tree **** "< while(1){ cout << " 1. Insert The Element"; cout << " 2. Search The Element"; cout << " 3. Print Tree in inorder:"; cout << " 4. Delete Node"; cout << " 5. Exit"; cout<<" Select your choice: "; cin>>option; switch (option){ case 1: do{ new_node = obj.get_node(); cout<<" Enter The Element"; cin>>new_node->data; if (root == NULL) root = new_node; else obj.insert(root, new_node); cout<<" Do you Want To insert More Elements?(y/n)"; ans = getch(); } while (ans == 'y'); break; case 2: cout<<" Enter Element to be searched :"; cin>>key; tmp=obj.search(root, key, &parent); cout<<" Parent of node "< break; case 3: if (root == NULL){ cout<<" Tree Is Empty"< } else{ cout<<" The Inorder display : "; obj.inorder(root); } break; case 4: if (root == NULL){ cout << " Tree Is Empty" << endl; } else{ int key; cout << "Enter element to be deleted: "; cin >> key; obj.delete_node(root, key); } break; case 5: exit(0); } } } The integers I want to search for are: 7369, 6960, 9877, 1900, 6859, 8399, 9268, 2662, 8863, 9758, 4839, 6152, 8597, 5751, 4618, 9483, 7448, 5054, 4284, 9728, 8089, 9604, 2359, 7172, 8144, 9814, 1753, 8512, 8757, 7170, 7775, 6357, 2553, 6167, 2293, 8528, 5761, 5765, 9697, 5543, 2747, 2950, 3696, 7271, 5615, 7441, 7244, 5492, 5330, 8716, 8655, 1566, 8268, 7367, 1275, 2947, 8088, 5538, 1573, 4404, 9625, 2714, 7847, 1022, 7621, 5373, 3115, 6299, 9909, 4959, 8605, 5119, 5616, 9527, 4106, 4870, 1605, 1883, 2278, 4328, 6438, 7200, 2886, 6147, 8701, 6573, 7774, 6717, 1375, 8670, 8826, 5094, 6685, 6948, 4463, 5696, 1998, 9239, 3956, 6860, 8344, 6698, 1894, 3926, 5418, 8745, 5605, 5647, 6202, 5255, 3750, 1264, 1150, 5362, 2884, 5879, 7933, 9756, 7711, 5542, 7378, 4847, 7670, 1197, 1326, 8227, 8036, 3578, 6540, 6655, 6176, 7676, 3040, 2742, 1631, 1701, 4164, 2536, 2291, 6961, 7668, 2512, 2759, 7730, 3030, 3411, 1152, 7123, 7669, 5797, 8093, 5389, 7529, 3509, 2535, 4230, 3218, 9902, 7655, 7183, 8443, 4467, 7456, 5271, 1257, 8077, 6204, 4371, 1419, 6500, 3026, 9398, 6249, 2736, 2497, 5122, 7338, 9821, 8786, 9642, 3139, 1674, 1791, 5848, 2303, 6875, 8620, 1068, 5304, 5728, 6713, 3414, 6593, 1885, 6481, 6517, 1458, 8051, 4146, 6876, 4999, 8730, 9464, 1789, 8191, 8835, 2979, 4154, 9330, 2525, 5799, 4150, 7355, 8848, 7141, 8495, 3627, 6996, 9969, 5481, 8855, 4841, 8266, 5811, 4456, 8463, 6684, 8781, 5097, 3875, 1986, 6626, 7557, 6688, 6165, 7702, 9486, 8608, 9620, 2941, 6157, 6638, 7517, 6840, 1137, 6199, 8331, 4349, 6366, 3420, 7364, 8770, 6221, 6863, 6365, 5397, 1108, 7481, 3481, 6621, 1201, 4274, 5457, 2946, 9624, 4885, 4646, 6180, 6296, 9915, 3044, 8502, 1565, 1916, 9465, 4824, 8402, 4176, 4107, 5155, 1297, 6428, 3717, 5876, 7541, 2814, 7867, 3429, 3760, 2270, 5244, 2583, 6837, 6514, 9365, 6853, 6530, 2308, 8450, 9924
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help