Write a class For implementing a simple binary search tree capable of storing nu
ID: 3715843 • Letter: W
Question
Write a class For implementing a simple binary search tree capable of storing numbers. The class should have member functions:
void insert (double x)
bool search (double x)
void inorder (vector <double> & v)
The insert function should not use recursion directly, or indirectly by calling a recursive function.
The search function should work by calling a private recursive member function
bool search (double x, BtreeNode *t)
The inorder function is passed an initially empty vector v: it fills v with the inorder list of numbers stored in the binary search tree. Demonstrate the operation of the class using a suitable driver program.
Explanation / Answer
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;
//class BinarySearchTree
class BinarySearchTree
{
private:
struct BST
{
BST* left;
BST* right;
int data;
};
BST* root;
//constructor
public:
BinarySearchTree()
{
root = NULL;
}
//prototypes
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(BST*);
void insert(int);
void search(int);
};
void BinarySearchTree::search(int d)
{
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
BST* curr;
BST* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
}
else
cout<<"Element "<<d<<" is found"<<endl;
}
void BinarySearchTree::insert(int d)
{
BST* t = new BST;
BST* 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
BST* 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;
cout<<"Element "<<d<<" is inserted into tree"<<endl;
}
}
void BinarySearchTree::print_inorder()
{
inorder(root);
}
void BinarySearchTree::inorder(BST* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}
int main()
{
BinarySearchTree bst;
int ch,insert,selement;
while(1)
{
//ask user to enter choice
cout<<endl<<endl;
cout<<" Simple Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Search "<<endl;
cout<<" 3. In-Order Traversal "<<endl;
cout<<" 4. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
//based on the choice control the flow of execution.
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>insert;
bst.insert(insert);
break;
case 3 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
bst.print_inorder();
break;
case 2 : cout<<endl;
cout<<" Enter Number to be search "<<endl;
cin>>selement;
bst.search(selement);
break;
case 4 : system("pause");
return 0;
break;
}//end of switch
}//end of while
}//end of main
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.