I have this BST #ifndef BST_H #define BST_H #include #include #include template
ID: 3876014 • Letter: I
Question
I have this BST
#ifndef BST_H
#define BST_H
#include
#include
#include
template
struct Node
{
Node();
DataType Item; //assumes a copy constructor has been written for a DataType
Node* Left;
Node* Right;
};
template
Node::Node()
{
Left = NULL;
Right = NULL;
}
template
class BST
{
typedef void(*FunctionType)(DataType& Item);
public:
BST();
~BST();
bool IsEmpty();
void Insert(const DataType& NewItem);
void Delete(const DataType& SearchItem);
bool Retrieve(const DataType& SearchItem, DataType& Result);
void PreorderTraverse(FunctionType Visit);
void InorderTraverse(FunctionType Visit);
void PostorderTraverse(FunctionType Visit);
private:
Node* Root;
void Destroy(Node*& pNode); //called in the destructor
void InsertItem(Node*& pNode, const DataType& NewItem);
void DeleteItem(Node*& pNode, const DataType& SearchItem);
void DeleteNodeItem(Node*& pNode);
void DeleteLeftMost(Node*& pNode, DataType& Item);
bool RetrieveItem(Node* pNode, const DataType& SearchItem, DataType& Item);
void Preorder(Node* pNode, FunctionType Visit);
void Inorder(Node* pNode, FunctionType Visit);
void Postorder(Node* pNode, FunctionType Visit);
};
template
BST::BST()
{
Root = NULL;
}
template
BST::~BST()
{
Destroy(Root);
}
template
bool BST::IsEmpty()
{
return (Root == NULL);
}
template
void BST::Insert(const DataType& NewItem)
{
InsertItem(Root, NewItem);
}
template
void BST::Delete(const DataType& SearchItem)
{
DeleteItem(Root, SearchItem);
}
template
bool BST::Retrieve(const DataType& SearchItem, DataType& Result)
{
return RetrieveItem(Root, SearchItem, Result);
}
template
void BST::PreorderTraverse(FunctionType Visit)
{
Preorder(Root, Visit);
}
template
void BST::InorderTraverse(FunctionType Visit)
{
Inorder(Root, Visit);
}
template
void BST::PostorderTraverse(FunctionType Visit)
{
Postorder(Root, Visit);
}
template
void BST::Destroy(Node*& pNode) //called in the destructor
{
if (pNode->Left != NULL)
{
Destroy(pNode->Left);
pNode->Left = NULL;
}
if (pNode->Right != NULL)
{
Destroy(pNode->Right);
pNode->Right = NULL;
}
if (pNode != NULL)
{
delete pNode;
pNode = NULL;
}
else
{
assert(false);
}
}
template
void BST::InsertItem(Node*& pNode, const DataType& NewItem)
{
if (pNode == NULL)
{
pNode = new Node();
pNode->Item = NewItem;
}
else if (NewItem < pNode->Item)
{
InsertItem(pNode->Left, NewItem);
}
else if (NewItem > pNode->Item)
{
InsertItem(pNode->Right, NewItem);
}
}
template
inline void BST::DeleteItem(Node*& pNode, const DataType & SearchItem)
{
}
template
inline void BST::DeleteNodeItem(Node*& pNode)
{
}
template
inline void BST::DeleteLeftMost(Node*& pNode, DataType & Item)
{
}
//operators == and > must be defined for DataType
template
bool BST::RetrieveItem(Node* pNode,
const DataType& SearchItem,
DataType& Item)
{
bool result = false;
if (pNode == NULL)
{
result = false;
}
else if (SearchItem == pNode->Item)
{
result = true;
Item = pNode->Item;
}
else if (SearchItem > pNode->Item)
{
result = RetrieveItem(pNode->Right, SearchItem, Item);
}
else
{
result = RetrieveItem(pNode->Left, SearchItem, Item);
}
return result;
}
template
void BST::Preorder(Node* pNode, FunctionType Visit)
{
if (pNode != NULL)
{
Visit(pNode->Item);
}
if (pNode->Left != NULL)
{
Preorder(pNode->Left, Visit);
}
if (pNode->Right != NULL)
{
Preorder(pNode->Right, Visit);
}
}
template
void BST::Inorder(Node* pNode, FunctionType Visit)
{
if (pNode->Left != NULL)
{
Inorder(pNode->Left, Visit);
}
if (pNode != NULL)
{
Visit(pNode->Item);
}
if (pNode->Right != NULL)
{
Inorder(pNode->Right, Visit);
}
}
template
void BST::Postorder(Node* pNode, FunctionType Visit)
{
if (pNode->Left != NULL)
{
Postorder(pNode->Left, Visit);
}
if (pNode->Right != NULL)
{
Postorder(pNode->Right, Visit);
}
if (pNode != NULL)
{
Visit(pNode->Item);
}
}
#endif
*
*
*
*
I need someone to code in these 3 deletion parts for me.
template
inline void BST::DeleteItem(Node*& pNode, const DataType & SearchItem)
{
}
template
inline void BST::DeleteNodeItem(Node*& pNode)
{
}
template
inline void BST::DeleteLeftMost(Node*& pNode, DataType & Item)
{
}
Thank you very much
Explanation / Answer
Case covering in the below code snippet -
node to be deleted is
struct Node
{
int key;
struct Node *left, *right;
};
/* Inorder traversal of BST */
struct Node * InorderTrav(struct Node* Node)
{
struct Node* current = Node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
/* Given a binary search tree and a SearchItem, this function deletes the SearchItem
and returns the new root
struct Node* root is root node of BST
int SearchItem is item to be deleted in BST
*/
struct Node* DeleteItem(struct Node* root, int SearchItem)
{
if (root == NULL) return root;
// If the SearchItem to be deleted is smaller than the root's SearchItem(left subtree)
if (SearchItem < root->key)
root->left = DeleteItem(root->left, SearchItem);
// If the SearchItem to be deleted is greater than the root's SearchItem(right subtree)
else if (SearchItem > root->key)
root->right = DeleteItem(root->right, SearchItem);
// if SearchItem is same as root's SearchItem, then delete it
else
{
if (root->left == NULL)//Node with no left child then copy right chlid in temp , delete the root
{
struct Node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)//Node with no right child then copy right chlid in temp , delete the root
{
struct Node *temp = root->left;
free(root);
return temp;
}
// Node with two children
struct Node* temp = InorderTrav(root->right);
// Copy the inorder successor's content to this Node
root->key = temp->key;
// Delete the inorder successor
root->right = DeleteItem(root->right, temp->key);
}
return root;
}