How do I modify the code below to search for integers from a txt file to see if
ID: 3917090 • Letter: H
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 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<iostream>
#include<stdlib.h>
#include<conio.h>
#include <cstdlib>
#include <fstream>
#include <sstream>
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 "<<temp->data<<"is Present"<<endl;
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<<" "<<temp->data;
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<<"------------------------------------------- "<<endl;
cout<<" **** Program For Binary Search Tree **** "<<endl;
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 "<<tmp->data<<" is"<<parent->data<<endl;
break;
case 3:
if (root == NULL){
cout<<" Tree Is Empty"<<endl;
}
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
Explanation / Answer
//first read each integer from text file one by one
fstream file;
string word, filename;
filename = "file.txt";
file.open(filename.c_str());
while (file >> word)
{
int length=word.length();
int num=0;
for(int i=0;i<length,i++){
num+=word.at(i)-'0';
if(i!=length-1)num*=10;
}
int count=0;
int result=search(root,num,count);
if(result==true)cout<<num<<" is found and total comparision "<<count<<" ";
else cout<<num<<" is not found and total comparision "<<count<<" ";
}
//search function with count number of comparision.
bool search(node*root,int key,int &count){
if(root==null)return false;
if(key<root->data)return search(root->left,key,++count);
if(key>root->data)return search(root->right,key,++count);
if(key==root->data){
count++;
return true;
}
}
/*for any query please comment.
please upvote if find it helpful.
Thank you.*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.