Given the following template BST skeleton, implement the %u201Cfind%u201D that w
ID: 3539930 • Letter: G
Question
Given the following template BST skeleton, implement the %u201Cfind%u201D that will return a pointer to the node in the BST if found. Note: the Node class is given as a reference
//simple class to represent a binary tree node
template <class T>
class Node {
public:
//constructor
Node(T data):left(NULL), right(NULL){ this->data = data; }
Node(): left(NULL), right(NULL){} //default constructor
//data members
T data; //the value of the node
Node<T> *left, *right; //left/right pointers
};
template<class Obj>
class BST{
public:
private:
int size; // the number of nodes in the tree
Node<Obj> *root; //root of the tree
};
Given the following template BST skeleton, implement the %u201Cfind%u201D that will return a pointer to the node in the BST if found. Note: the Node class is given as a reference
//simple class to represent a binary tree node
template <class T>
class Node {
public:
//constructor
Node(T data):left(NULL), right(NULL){ this->data = data; }
Node(): left(NULL), right(NULL){} //default constructor
//data members
T data; //the value of the node
Node<T> *left, *right; //left/right pointers
};
template<class Obj>
class BST{
public:
private:
int size; // the number of nodes in the tree
Node<Obj> *root; //root of the tree
};
Explanation / Answer
#include<iostream>
using namespace std;
template <class T>
class Node {
public:
//constructor
Node(T data):left(NULL), right(NULL){ this->data = data; }
Node(): left(NULL), right(NULL){} //default constructor
//data members
T data; //the value of the node
Node<T> *left, *right; //left/right pointers
};
template<class Obj>
class BST{
public:
BST(){root=NULL; size=0;}
void insert(Obj o);
Node<Obj>* search(Node<Obj>& o);
void inorderDisplay();
private:
int size; // the number of nodes in the tree
Node<Obj> *root; //root of the tree
void inorderDisplayHelp(Node<Obj> *root);
};
template<class Obj>
void BST<Obj>::insert(Obj o)
{
Node<Obj>* current=root;
Node<Obj>* temp=new Node<Obj>(o);
if(current==NULL)
root=temp;
else
{
while(current!=NULL)
{
if(current->data>o)
{
if(current->left==NULL)
{
current->left=temp;
break;
}
else
current=current->left;
}
else
{
if(current->right==NULL)
{
current->right=temp;
break;
}
else
current=current->right;
}
}
size++;
}
}
template <class Obj>
Node<Obj>* BST<Obj>::search(Node<Obj>& o)
{
Node<Obj>*current=root;
while(current!=NULL)
{
if(o.data==current->data)
return root;
else if(o.data<current->data)
current=current->left;
else
current=current->right;
}
return NULL;
}
template<class Obj>
void BST<Obj>::inorderDisplay()
{
inorderDisplayHelp(root);
}
template<class Obj>
void BST<Obj>::inorderDisplayHelp(Node<Obj> *root)
{
if (root==NULL)
return;
inorderDisplayHelp(root->left);
cout<<root->data<<" ";
inorderDisplayHelp(root->right);
}
int main()
{
BST<int> b;
b.insert(2);
b.insert(6);
b.insert(9);
b.insert(3);
b.insert(99);
cout<<"binary search tree elements: ";
b.inorderDisplay();
cout<<endl;
cout<<"Enter the element to be searched: ";
int n;
cin>>n;
Node<int> node(n);
if(b.search(node))
cout<<"data found "<<endl;
else
cout<<"data not found"<<endl;
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.