Question: I am writing binary search tree deleting a key using windows 10 and C (visual studio 2015) but It has some errors. First, It says
I am writing binary search tree deleting a key using windows 10 and C (visual studio 2015) but It has some errors.
First, It says NULL is not defined.
Second, It says you can't use pointer about incomplete class type about del, freeNode, parent, root, parentNode and rootPtr.
Can you correct these errors?
The following is my code.
-----------------------------------------------------------------------------------------------------------------------------------------------------
typedef struct NODE* PNODE;
typedef struct _NODE {
int key;
NODE* leftChild;
NODE* rightChild;
} NODE;
PNODE g_root;
void DeleteNode(PNODE* root, int key) {
PNODE freeNode = NULL;
PNODE del = Search(g_root, key);
PNODE parent = NULL;
PNODE child = NULL;
if (!del) {
printf("No NODE that has a key ");
return;
}
if ((del->leftChild == NULL) || (del->rightChild == NULL)) {
freeNode = del;
}
else {
freeNode = Successor(del);
}
if (freeNode->leftChild != NULL) {
child = freeNode->leftChild;
}
else {
child = freeNode->rightChild;
}
parent = SearchParent(g_root, freeNode->key);
if (parent == NULL) {
root = child;
}
else {
if (freeNode == parent->leftChild) {
parent->leftChild = child;
}
else {
parent->rightChild = child;
}
}
if (freeNode != del) {
del->key = freeNode->key;
}
if (freeNode)free(freeNode);
}
PNODE Successor(PNODE root) {
if (root->rightChild) {
return MinimumNode(root->rightChild);
}
PNODE parentNode = SearchParent(g_root, root->key);
while ((parentNode != NULL) && (parentNode->rightChild == root)) {
root = parentNode;
parentNode = SearchParent(g_root, root->key);
}
return parentNode;
}
PNODE MinimumNode(PNODE rootPtr) {
while ((rootPtr->leftChild) != NULL) {
rootPtr = rootPtr->leftChild;
}
return rootPtr;
}
PNODE SearchParent(PNODE rootPtr, int key) {
PNODE parentPtr = NULL;
while (rootPtr) {
if (key == rootPtr->key) {
return parentPtr;
}
parentPtr = rootPtr;
if (key < rootPtr->key) {
rootPtr = rootPtr->leftChild;
}
else {
rootPtr = rootPtr->rightChild;
}
}
return NULL;
}
PNODE Search(PNODE rootPtr, int key) {
while (rootPtr) {
if (key == rootPtr->key) {
return rootPtr;
}
if (key < rootPtr->key) {
rootPtr = rootPtr->leftChild;
}
else {
rootPtr = rootPtr->rightChild;
}
}
return NULL;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help