I have to write a program that creates a binary search tree from a file and output it and several other requirements. One requirement that I cannot figure out is how to find the search cost for each node. These are the instructions I was given
Calculate the search cost for each node when it is inserted
– A binary node element has at least two data fields: Key and SearchCost
– For each node, count and store the number of comparisons required when searching for the
node (i.e., the number of comparisons = the search cost for the node = 1+ the depth of the
node)
And the output is supposed to be:
Input data: 5, 3, 9, 7
Create a binary search tree:
Key = 5 SearchCost = 1
Key = 3 SearchCost = 2
Key = 9 SearchCost = 2
Key = 7 SearchCost = 3
Total number of nodes is 4
To generate output on the screen we use the in-order traversal. Here each node is represented as
Key[SearchCost]:
3[2] 5[1] 7[3] 9[2]
I can currently print the input in in-order transversal however I cannot for the life of me figure out how to calculate the search cost and I cannot figure out how to assign these values to the keys. This is part of my code currently:
class BinarySearchTree
{
private:
struct BinaryNode
{
BinaryNode* left;
BinaryNode* right;
int data;
};
BinaryNode* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(BinaryNode*);
void insert(int);
void remove(int);
void printTree(BinaryNode*);
void print_Tree(int level);
void showtree(BinaryNode*, int level);
void tree_line(BinaryNode*, int level);
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
BinaryNode* t = new BinaryNode;
BinaryNode* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
BinaryNode* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
int main()
{
BinarySearchTree b;
int temp;
int count = 0;
ifstream input;
string fileName;
cout<< endl<< "This program will read data from a user desginated file and create a binary search tree based on the input data." <<endl;
cout << endl << "Please enter a file name: ";
cin >> fileName;
cout << "The input data from the file is: " << endl;
input.open(fileName.c_str());
if(input.is_open()){
while(input >> temp){
cout<< temp << ", ";
b.insert(temp);
count++;
}
input.close();
}
else{
cout << "Error opening file";
}
int ch,tmp1;
int level = 1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. In-Order Traversal "<<endl;
cout<<" 2. Output Tree " <<endl;
cout<<" 3. Removal "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 2: cout << endl;
cout<<" Tree "<<endl;
cout<<" -------------------"<<endl;
b.print_Tree(level);
break;
case 3 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 4 :
return 0;
}
}
}
I have really been struggling with this and if anyone could help me I would really appreciate it!
