Hi Guys, can you please point out what could be the issue with code below. I guess I m doing something wrong with pointers maintenance however from my perspective this code should be ok.
What I am doing is:
1. Create tree and populate it with nodes. -- OK
2. Print tree. --- OK
3. Locate node to be removed. -- OK
3. Delete particular node (logic seems to be OK) however I get segmentation fault all the time once I am trying to free() node that has to be removed.
Please help.
Code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node *tree;
struct node {
int key;
tree left;
tree right;
};
void InsertKey(tree *tr, int key) {
if (*tr == NULL) {
if ( (*tr=(tree)malloc(sizeof(tree))) == NULL) {
printf("Can not allocate root\n");
exit(1);
}
(*tr)->key=key;
(*tr)->left=NULL;
(*tr)->right=NULL;
}
else {
if (key<(*tr)->key)
InsertKey(&(*tr)->left, key);
else
InsertKey(&(*tr)->right, key);
}
}
void PrintKey(tree *tr) {
if (*tr == NULL)
return;
else {
printf("Value of item is %d\n", (*tr)->key);
PrintKey(&(*tr)->left);
/*printf("Value of item is %d\n", (*tr)->key);*/
PrintKey(&(*tr)->right);
}
}
tree SearchTree(tree tr, int key) {
if (tr==NULL) /* tree is empty*/
return NULL;
else if (tr->key>key) /* search left subtree*/
return SearchTree(tr->left, key);
else if (tr->key<key) /* search right subtree*/
return SearchTree(tr->right, key);
else
return tr;
}
void DeleteNodeR(tree *tr) {
if ((*tr)->left==NULL && (*tr)->right==NULL) {
tree tmp=*tr;
*tr=NULL;
free(tmp);
tmp=NULL;
}
else if ((*tr)->left==NULL) {
tree root=*tr;
*tr=(*tr)->right;
free(root);
}
else if ((*tr)->right==NULL) {
tree root=*tr;
*tr=(*tr)->left;
free(root);
}
else { /* node has both children, get right most node from left subtree */
tree iterateLeftTree=(*tr)->left;
while (iterateLeftTree->right!=NULL)
iterateLeftTree=iterateLeftTree->right;
(*tr)->key=iterateLeftTree->key;
free(iterateLeftTree);
iterateLeftTree=NULL;
}
}
int main(void) {
tree tr=NULL;
tree locatedNode=NULL;
InsertKey(&tr, 15);
InsertKey(&tr, 20);
InsertKey(&tr, 10);
PrintKey(&tr);
locatedNode=SearchTree(tr,10);
printf("Remove node %d\nTree after removal\n", locatedNode->key);
DeleteNodeR(&locatedNode);
PrintKey(&tr);
return 0;
}
Thank you.