Help BST Tree Function template ItemType BinaryNodeTreemoveV

Help! BST Tree Function:

template<class ItemType>
ItemType BinaryNodeTree<ItemType>::moveValuesUpTree(BinaryNode<ItemType> subTreePtr)
{

}

Here are the header files:

// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.

// Listing 16-3.

/** ADT binary tree: Link-based implementation.
@file BinaryNodeTree.h */

#ifndef BINARY_NODE_TREE_H
#define BINARY_NODE_TREE_H

#include \"BinaryTreeInterface.h\"
#include \"BinaryNode.h\"
#include \"PrecondViolatedExcep.h\"
#include \"NotFoundException.h\"
#include <memory>

template<class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
BinaryNode<ItemType> rootPtr;

protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
int getHeightHelper(BinaryNode<ItemType> subTreePtr) const; //done
int getNumberOfNodesHelper(BinaryNode<ItemType> subTreePtr) const;

// Recursively adds a new node to the tree in a left/right fashion to keep tree balanced.
ItemType balancedAdd(BinaryNode<ItemType> subTreePtr,
BinaryNode<ItemType> newNodePtr); //done

// Removes the target value from the tree.
virtual ItemType removeValue(BinaryNode<ItemType> subTreePtr,
const ItemType target, bool& isSuccessful); //done

// Copies values up the tree to overwrite value in current node until
// a leaf is reached; the leaf is then removed, since its value is stored in the parent.
ItemType moveValuesUpTree(BinaryNode<ItemType> subTreePtr);

// Recursively searches for target value.
virtual ItemType findNode(BinaryNode<ItemType> treePtr,
const ItemType& target, bool& isSuccessful) const; //done

// Copies the tree rooted at treePtr and returns a pointer to the root of the copy.
//BinaryNode<ItemType> copyTree(const BinaryNode<ItemType>* treePtr) const;

// Recursively deletes all nodes from the tree.
void destroyTree(BinaryNode<ItemType> subTreePtr); //done

// Recursive traversal helper methods:
void preorder(void visit(ItemType&), BinaryNode<ItemType> treePtr) const; //done
void inorder(void visit(ItemType&), BinaryNode<ItemType> treePtr) const; //done
void postorder(void visit(ItemType&), BinaryNode<ItemType> treePtr) const; //done

public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinaryNodeTree(); //done
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem,
const BinaryNodeTree<ItemType> leftTreePtr,
const BinaryNodeTree<ItemType> rightTreePtr); //done
BinaryNodeTree(const BinaryNodeTree<ItemType>& tree); //done
virtual ~BinaryNodeTree(); //done

//------------------------------------------------------------
// Public BinaryTreeInterface Methods Section.
//------------------------------------------------------------
bool isEmpty() const; //done
int getHeight() const; //done
int getNumberOfNodes() const;

ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData);

bool add(const ItemType& newData); // Adds an item to the tree //done
bool remove(const ItemType& data); // Removes specified item from the tree //done
void clear();

ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
bool contains(const ItemType& anEntry) const;

//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const; //done
void postorderTraverse(void visit(ItemType&)) const;

//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);
}; // end BinaryNodeTree

#include \"BinaryNodeTree.cpp\"
#endif

__________________________________________________________________

// Created by Frank M. Carrano and Tim Henry.
// Copyright (c) 2013 __Pearson Education__. All rights reserved.

// Listing 16-4.

/** Link-based implementation of the ADT binary search tree.
@file BinarySearchTree.h */

#ifndef _BINARY_SEARCH_TREE_H
#define _BINARY_SEARCH_TREE_H

#include \"BinaryTreeInterface.h\"
#include \"BinaryNode.h\"
#include \"BinaryNodeTree.h\"
#include \"NotFoundException.h\"
#include \"PrecondViolatedExcep.h\"

template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;

protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Recursively finds where the given node should be placed and
// inserts it in a leaf at that point.
BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
BinaryNode<ItemType>* newNode);

// Removes the given target value from the tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,
const ItemType target,
bool& success);

// Removes a given node from a tree while maintaining a
// binary search tree.
BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodePtr);

// Removes the leftmost node in the left subtree of the node
// pointed to by nodePtr.
// Sets inorderSuccessor to the value in this node.
// Returns a pointer to the revised subtree.
BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr,
ItemType& inorderSuccessor);

// Returns a pointer to the node containing the given value,
// or nullptr if not found.
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
const ItemType& target) const;

public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& tree);
virtual ~BinarySearchTree();

//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const;// throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData) const;// throw(PrecondViolatedExcep);
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
ItemType getEntry(const ItemType& anEntry) const;// throw(NotFoundException);
bool contains(const ItemType& anEntry) const;
void clear();

//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;

//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree<ItemType>& operator=(const BinarySearchTree<ItemType>& rightHandSide);   
}; // end BinarySearchTree

#include \"BinarySearchTree.cpp\"

#endif

________________________________________________________________________

// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.

// Listing 16-2.

/** A class of nodes for a link-based binary tree.
@file BinaryNode.h */

#ifndef BINARY_NODE_H
#define BINARY_NODE_H
#include <memory>

template<class ItemType>
class BinaryNode
{
private:
ItemType item; // Data portion
BinaryNode<ItemType> leftChildPtr; // Pointer to left child
BinaryNode<ItemType> rightChildPtr; // Pointer to right child

public:
BinaryNode();
BinaryNode(const ItemType& anItem);
BinaryNode(const ItemType& anItem,
BinaryNode<ItemType> leftPtr,
BinaryNode<ItemType> rightPtr);

void setItem(const ItemType& anItem);
ItemType getItem() const;

bool isLeaf() const;

ItemType getLeftChildPtr() const;
ItemType getRightChildPtr() const;

void setLeftChildPtr(BinaryNode<ItemType> leftPtr);
void setRightChildPtr(BinaryNode<ItemType> rightPtr);
}; // end BinaryNode

#include \"BinaryNode.cpp\"
#endif

___________________________________________________________________________________________

Solution

/*
* C++ Program To Implement BST
*/
# 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 find(int, node **, node **);
void insert(int);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(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.Delete Element \"<<endl;
cout<<\"3.Inorder Traversal\"<<endl;
cout<<\"4.Preorder Traversal\"<<endl;
cout<<\"5.Postorder Traversal\"<<endl;
cout<<\"6.Display\"<<endl;
cout<<\"7.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);
case 2:
if (root == NULL)
{
cout<<\"Tree is empty, nothing to delete\"<<endl;
continue;
}
cout<<\"Enter the number to be deleted : \";
cin>>num;
bst.del(num);
break;
case 3:
cout<<\"Inorder Traversal of BST:\"<<endl;
bst.inorder(root);
cout<<endl;
break;
   case 4:
cout<<\"Preorder Traversal of BST:\"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<\"Postorder Traversal of BST:\"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<\"Display BST:\"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<\"Wrong choice\"<<endl;
}
}
}

/*
* Find Element in the Tree
*/
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
   else
   ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}

/*
* 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;
}  
}
}

/*
* Delete Element from the tree
*/
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<\"Tree empty\"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<\"Item not present in tree\"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}

/*
* Case A
*/
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}

/*
* Case B
*/
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}

/*
* Case C
*/
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}

/*
* Pre Order Traversal
*/
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<\"Tree is empty\"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<\" \";
preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* 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);
}
}

/*
* Postorder Traversal
*/
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<\"Tree is empty\"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<\" \";
}
}

/*
* 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);
}
}