Reputation: 3301
I am implementing a function for the node removal from the binary search tree. The prototype of the function is set and I can't change it, it is a school assignment. My code:
typedef struct tBSTNode {
char Key;
struct tBSTNode * LPtr;
struct tBSTNode * RPtr;
} *tBSTNodePtr;
void BSTDelete (tBSTNodePtr *RootPtr, char K) {
tBSTNodePtr *tmp;
if (*RootPtr != NULL) {
if (K < (*RootPtr)->Key)
BSTDelete(&(* RootPtr)->LPtr, K);
else if (K > (*RootPtr)->Key)
BSTDelete(&(* RootPtr)->RPtr, K);
else {
if ((* RootPtr)->LPtr == NULL) {
/* there is only right branch or none*/
tmp = RootPtr;
*RootPtr = (* RootPtr)->RPtr;
free(*tmp);
*tmp = NULL;
}
else if ((* RootPtr)->RPtr == NULL) {
/* there is only left branch or none*/
tmp = RootPtr;
*RootPtr = (* RootPtr)->LPtr;
free(*tmp);
*tmp = NULL;
}
else
/* there are both branches, but that is for another topic*/
}
}
}
This code works correctly just in case when there are no branches connected to the node I am deleting. I expect that there is a problem with *tmp = NULL; line and I am losing my address to the rest of the branch but on the other hand if this line isn't included I am getting a SEGFAULT and I am trying to figure out why.
EDIT:
ok, now I know where the mistake was. It is stupid mistake, I should have used tBSTNodePtr tmp; instead of tBSTNodePtr *tmp;
Upvotes: 0
Views: 351
Reputation: 230
you have problems with using pointers. If we have sometype *ptr
and we check if this ptr adresses some space we write (ptr!=NULL)
.
*ptr
is refering to the value itself, for example to your structre.
Read more about pointer types in C.
Upvotes: 1
Reputation: 5183
your logic for deleting is wrong
if ((* RootPtr)->LPtr == NULL) {
/* there is only right branch or none*/
tmp = RootPtr;
*RootPtr = (* RootPtr)->RPtr;
free(*tmp);
*tmp = NULL;
}
in this code you are deleting the required node but not adding the child root of that node
if ((* RootPtr)->LPtr == NULL) {
/* there is only right branch or none*/
tmp = RootPtr;
*RootPtr = (* RootPtr)->RPtr;
free(*tmp);
*tmp = NULL;
insert(RootPtr); //insert the child node again in the tree
}
Upvotes: 0