Write a class For implementing a simple binary search tree capable of storing nu
ID: 3681731 • 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 & 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.
Here is my code so far:
#include <iostream>
#include <vector>
using namespace std;
class BinaryTree
{
private:
// Structure for tree nodes
struct BtreeNode
{
BtreeNode *left;
BtreeNode *right;
int value;
};
BtreeNode* root; // Pointer to the root of the tree
public:
// Constructor
BinaryTree() { root = NULL; }
// Member functions
bool isEmpty() const { return root == NULL; }
void insert(double x);
bool search(double x);
void inorder(vector <double> & v);
};
void BinaryTree::insert(double x)
{
BtreeNode* t = new BtreeNode;
BtreeNode* parent;
t->value = x;
t->left = NULL;
t->right = NULL;
parent = NULL;
// If it is a new tree
if (isEmpty())
{
root = t;
}
else
{
BtreeNode* current;
current = root;
while (current)
{
parent = current;
if (t->value > current->value)
current = current->right;
else
current = current->left;
}
}
}
bool BinaryTree::search(double x)
{
}
void BinaryTree::inorder(vector <double> & v)
{
}
Can anyone help me with the search and inorder functions the way they ask me to do them in the question?
Explanation / Answer
Inorder Traversal:
Program code in c++:
/*
* C++ Program to Perform Inorder Recursive Traversal of a Given Binary Tree
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
/*
* Class Declaration
*/
class BST
{
public:
void insert(node *, node *);
void inorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Inorder Traversal"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insert(root, temp);
break;
case 2:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 3:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 4:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.