Code for deleting a tree node not working
Hello,
I've come on here as a last resort for help as to why my code for deleting a tree doesn't work :(. Sometimes I get seg fault and sometimes it deletes extra nodes... Could someone please take a look at my code and let me know what's wrong?
I've been scratching my head for a week. The logic seems right but something's missing...
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct treeNode {
struct treeNode *leftPtr; /* pointer to left subtree */
int data; /* node value */
int height;
struct treeNode *rightPtr; /* pointer to right subtree */
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
TreeNodePtr searchPar(TreeNodePtr rootPtr, int value);
TreeNodePtr search(TreeNodePtr rootPtr, int value);
void delete(TreeNodePtr rootPtr, int value);
int smallest(TreeNodePtr treePtr);
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
int main(int argc, char *argv[]) {
int value;
int i; /* counter to loop from 1-10 */
int item;
TreeNodePtr rootPtr = NULL; /* tree initially empty */
srand(time(NULL));
printf( "The numbers being placed in the tree are:\n" );
/* insert random values between 0 and 14 in the tree */
for ( i = 0; i <= 8; i++ ) {
item = rand() % 15;
printf( "%3d ", item);
insertNode( &rootPtr, item );
}
printf("\n");
postOrder(rootPtr);
printf("\n");
printf("Enter value to be deleted: ");
scanf("%d", &value);
delete(rootPtr, value);
preOrder(rootPtr);
printf("\n");
return 0;
}
void delete(TreeNodePtr rootPtr, int value) {
TreeNodePtr parentPtr = NULL;
TreeNodePtr currPtr = NULL;
TreeNodePtr tempPtr = NULL;
int smallestVal;
/* We must first find the parent node of the desired node */
parentPtr=searchPar(rootPtr, value);
/* Now find the actual node to be deleted. */
currPtr=search(parentPtr, value);
/* If node is a leaf */
if (currPtr->leftPtr==NULL && currPtr->rightPtr==NULL) {
printf("leaf\n");
tempPtr=currPtr;
/* We now must point the leftPtr or rightPtr of the parent node to NULL. */
if (parentPtr!=NULL && parentPtr->leftPtr->data==currPtr->data) {
parentPtr->leftPtr=NULL;
} else if (parentPtr!=NULL && parentPtr->rightPtr->data==currPtr->data) {
parentPtr->rightPtr=NULL;
} else if (parentPtr!=NULL && parentPtr->data==currPtr->data) {
parentPtr=NULL;
}
free(tempPtr);
/* If node has one child */
} else if (currPtr->leftPtr==NULL || currPtr->rightPtr==NULL ) {
printf("one child\n");
tempPtr=currPtr;
/* If leftPtr of parent points to node. */
if (parentPtr->leftPtr!=NULL && parentPtr->leftPtr->data==currPtr->data) {
/* If the node has a child on its rightPtr */
if (currPtr->leftPtr==NULL) {
parentPtr->leftPtr=currPtr->rightPtr;
/* If the node has a child on its leftPtr */
} else {
parentPtr->leftPtr=currPtr->leftPtr;
}
/* If rightPtr of parent points to node. */
} else if (parentPtr->rightPtr!=NULL && parentPtr->rightPtr->data==currPtr->data) {
/* If the node has a child on its rightPtr */
if (currPtr->rightPtr==NULL) {
parentPtr->rightPtr=currPtr->rightPtr;
/* If the node has a child on its leftPtr */
} else {
parentPtr->rightPtr=currPtr->leftPtr;
}
}
free(tempPtr);
/* If node has two children */
} else {
printf("two children\n");
smallestVal=smallest(currPtr);
delete(currPtr, smallestVal);
currPtr->data=smallestVal;
}
}
void insertNode( TreeNodePtr *treePtr, int value ) {
if ( *treePtr == NULL ) {
*treePtr = malloc( sizeof( TreeNode ) );
/* if memory was allocated then assign data */
if ( *treePtr != NULL ) {
( *treePtr )->data = value;
( *treePtr )->leftPtr = NULL;
( *treePtr )->rightPtr = NULL;
} else {
printf( "%d not inserted. No memory available.\n", value );
} /* end else */
} else { /* tree is not empty */
/* data to insert is less than data in current node */
if ( value < ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->leftPtr ), value );
} /* end if */
/* data to insert is greater than data in current node */
else if ( value > ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->rightPtr ), value );
} else { /* duplicate data value ignored */
printf( "dup" );
} /* end else */
} /* end else */
}
/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
inOrder( treePtr->leftPtr );
printf( "%3d", treePtr->data );
inOrder( treePtr->rightPtr );
} /* end if */
} /* end function inOrder */
/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
postOrder( treePtr->leftPtr );
postOrder( treePtr->rightPtr );
printf( "%3d ", treePtr->data );
} /* end if */
} /* end function postOrder */
/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
printf( "%3d", treePtr->data );
preOrder( treePtr->leftPtr );
preOrder( treePtr->rightPtr );
} /* end if */
} /* end function preOrder */
Thanks a lot.
