Code for deleting a tree node not working

This is a discussion on Code for deleting a tree node not working within the C Programming forums, part of the General Programming Boards category; Hello, I've come on here as a last resort for help as to why my code for deleting a tree ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    79

    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.
    Last edited by Mini; 10-09-2010 at 07:28 AM.

  2. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    79
    Also... would this be the standard way that one would do tree removal? If not, is there an alternative/easier way?

    Thanks

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    Code:
      2
     / \
    1   3
    If you delete 2, the root node, then your delete function first has to deal with the possibility of removing the root node.

    The second point is that having removed a node with LEFT and RIGHT branches, you need some way of rejoining the tree together, with either 1 or 3 as the new root.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting the parent of a node in a binary tree
    By budala in forum C Programming
    Replies: 4
    Last Post: 09-18-2009, 12:36 PM
  2. Memory Leak
    By jtullo in forum C Programming
    Replies: 7
    Last Post: 12-11-2006, 10:45 PM
  3. I need help~~Hash~~THX!
    By freefallin in forum C Programming
    Replies: 5
    Last Post: 04-22-2004, 07:50 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM
  5. why is the input not working
    By mackol in forum C Programming
    Replies: 7
    Last Post: 11-07-2002, 03:28 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21