please provide a "Implement Augmented Private and Public Bstree Function". I have already started the Bstree.cpp code, please just add the PRIVATE and PUBLIC function! Bstree.cpp (add the Private and Public functions at the end of this code):
please provide a "Implement Augmented Private and Public Bstree Function". I have already started the Bstree.cpp code, please just add the PRIVATE and PUBLIC function!
Bstree.cpp (add the Private and Public functions at the end of this code):
using namespace std;
#include "Bstree.h"
/* Nested Node class definitions */
template <typename U>
template <typename T>
Bstree<U>::Node<T>::Node(T item)
{
data = item;
left = nullptr;
right = nullptr;
}
/* Outer Bstree class definitions */
template <typename T>
Bstree<T>::Bstree()
{
root = nullptr;
order = 0;
}
template <typename T>
Bstree<T>::~Bstree()
{
recDestroy(root);
}
template <typename T>
bool Bstree<T>::empty() const
{
return root == nullptr;
}
template<typename T>
void Bstree<T>::insert(T item)
{
Node<T>* tmp;
Node<T>* newnode = new Node<T>(item);
/* If it is the first node in the tree */
if (!root)
{
root = newnode;
order++;
return;
}
/*find where it should go */
tmp = root;
while (true)
{
if (tmp->data == item)
{ /* Key already exists. */
tmp->data = item;
delete newnode; /* dont need it */
return;
}
else if (tmp->data > item)
{
if (!(tmp->left))
{/* If the key is less than tmp */
tmp->left = newnode;
order++;
return;
}
else
{/* continue searching for insertion pt. */
tmp = tmp->left;
}
}
else
{
if (!(tmp->right))
{/* If the key is greater than tmp */
tmp->right = newnode;
order++;
return;
}
else
{/* continue searching for insertion point*/
tmp = tmp->right;
}
}
}
}
template<typename T>
bool Bstree<T>::inTree(T item) const
{
Node<T>* tmp;
if (!root)
return false;
/*find where it is */
tmp = root;
while (true)
{
if (tmp->data == item)
return true;
else if (tmp->data > item)
{
if (!(tmp->left))
return false;
else
{/* continue searching */
tmp = tmp->left;
}
}
else
{
if (!(tmp->right))
return false;
else
/* continue searching for insertion pt. */
tmp = tmp->right;
}
}
}
template<typename T>
bool Bstree<T>::remove(const T& item)
{
Node<T>* nodeptr = search(item);
if (nodeptr)
{
remove(nodeptr);
order--;
return true;
}
return false;
}
template<typename T>
const T& Bstree<T>::retrieve(const T& key) const
{
Node<T>* nodeptr;
if (!root)
throw BstreeException("Exception:tree empty on retrieve().");
nodeptr = search(key);
if (!nodeptr)
throw BstreeException("Exception: non-existent key on retrieve().");
return nodeptr->data;
}
template<typename T>
void Bstree<T>::inorderTraverse(FuncType apply) const
{
inorderTraverse(root,apply);
}
template<typename T>
long Bstree<T>::size() const
{
return order;
}
template<typename T>
bool Bstree<T>::remove(Node<T>* node)
{
T data;
Node<T> replacement;
Node<T> parent = findParent(node);
if (!parent)
return false;
if (node->left && node->right) /two children case/
{
Node<T>* lchild = node->left;
Node<T>* lprnt = node;
while(lchild->right)
{
lprnt = lchild;
lchild = lchild->right;
}
data = node->data;
node->data = lchild->data;
node = lchild;
parent = lprnt;
}
/* one or zero child case /
replacement = node->left;
if (!replacement)
replacement = node->right;
if (parent == nullptr) / root */
{
delete node;
root = replacement;
return true;
}
if (parent->left == node)
parent->left = replacement;
else
parent->right = replacement;
delete node;
return true;
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
