I need someone to create the Delete Node Code For me in this binary search tree.

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

Navigate

• Browse (All)
• Browse I
• Subjects

---