I need someone to create the Delete Node Code For me in this binary search tree.
ID: 3876031 • Letter: I
Question
I need someone to create the Delete Node Code For me in this binary search tree. It is the only missing puzzle from my project and I spent 3 days thinking about it but couldn't come up with a solution.
*
*
*
*
This is the missing piece
*
*
*
template
inline void BST::DeleteItem(Node*& pNode, const DataType & SearchItem)
{
}
template
inline void BST::DeleteNodeItem(Node*& pNode)
{
}
*
*
*
*
*
*
And this the full code of the binary search tree that i wrote
*
*
*
*
*
home / study / engineering / computer science / computer science questions and answers / i have this bst #ifndef bst_h #define bst_h #include #include #include template struct node ...
Question: I have this BST #ifndef BST_H #define BST_H #include #include #include template struct Node { Nod...
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
Explanation / Answer
/* Binary Search Tree - BST implementation Using C language. Delete any node of a BST Programmed by Hasan Abdullah Contact: http://hellohasan.com */ #include #include typedef struct bst { int number; struct bst *leftChild; struct bst *rightChild; } node; node *root = NULL; void insertNode(int value); void preOrderPrint(node *root); node * findMinimum(node *root); node * deleteNode(node *root, int value); int main() { //Create a BST using: 47 40 54 38 43 49 39 45 44 30 41 70 46 59 insertNode(47); insertNode(40); insertNode(54); insertNode(38); insertNode(43); insertNode(49); insertNode(39); insertNode(45); insertNode(44); insertNode(30); insertNode(41); insertNode(70); insertNode(46); insertNode(59); printf(" Pre-Order Tree printing: "); preOrderPrint(root); puts(""); //Delete 43 from created BST root = deleteNode(root, 43); printf(" Pre-Order Tree printing after deletion: "); preOrderPrint(root); puts(""); return 0; } node * deleteNode(node *currentNode, int value) { if(currentNode==NULL) // empty tree return NULL; else if(value number) // value is less than node's number. so go to left subtree currentNode->leftChild = deleteNode(currentNode->leftChild, value); else if(value > currentNode->number) // value is greater than node's number. so go to right subtree currentNode->rightChild = deleteNode(currentNode->rightChild, value); else // node found. Let's delete it! { //node has no child if(currentNode->leftChild == NULL && currentNode->rightChild == NULL) { currentNode = NULL; } else if(currentNode->leftChild == NULL) // node has only right child { currentNode = currentNode->rightChild; } else if(currentNode->rightChild == NULL) // node has only left child { currentNode = currentNode->leftChild; } else // node has two children { node *tempNode = findMinimum(currentNode->rightChild); currentNode->number = tempNode->number; currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number); } } return currentNode; } node * findMinimum(node *currentNode) { if(currentNode->leftChild==NULL) return currentNode; return findMinimum(currentNode->leftChild); } void insertNode(int value) { node *tempNode; node *currentNode; node *parentNode; tempNode = (node *) malloc(sizeof(node)); tempNode->number = value; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //For the very first call if(root==NULL) { root = tempNode; } else { currentNode = root; parentNode = NULL; while(1) { parentNode = currentNode; if(value number) { currentNode = currentNode->leftChild; if(currentNode==NULL) { parentNode->leftChild = tempNode; return; } } else { currentNode = currentNode->rightChild; if(currentNode==NULL) { parentNode->rightChild = tempNode; return; } } } } } void preOrderPrint(node *root) { if(root==NULL) return; printf("%d ", root->number); preOrderPrint(root->leftChild); preOrderPrint(root->rightChild); }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.