c - Getting weird results in binary tree removal method -

i rewrote binary tree implementation, , it's close, removal of subtrees still lacking complete functionality.

removing tree no children not work @ all. in fact, when calling method search tree instances of removed tree, search method returns true (even though tree , item contained within tree freed @ end of removal method). can't solve one, gdb.

removing tree 1 child works, if it's root node.

removing tree 2 children partially works. left tree, pointer, of removed tree set pointer removed tree, pointer held in higher tree removed tree. however, right of removed tree lost.

tree.h

/*-------------------------------tree.h---------------------------------*/   #ifndef tree #define tree  #define maxlevel 4 typedef struct cat{     char *name;      int age;  }item;  /*user comparison function*/  typedef int (*comp)(const item *, const item *);   typedef struct tree{     int branches;      item *item;      struct tree *left, *right;  }tree;    tree *initializetree(tree *);  int isempty(tree *);  int isfull(tree *);  tree **searchtree(tree **, item *, comp);  int addtotree(tree **, item *, comp); int removefromtree(tree **, item *, comp);  void printtree(tree *, int);  tree *copytotree(item *);  int returncount(tree *);  #endif 

tree.c

/*-------------------------------tree.c---------------------------------*/ #include <stdio.h> #include <stdlib.h> #include "tree.h" #include <math.h>  tree *initializetree(tree *t){     if((t = malloc(sizeof(tree))) == null)             return null;       t->left = t->right = null;     t->item = null;     t->branches = 0;       return t;   }  int isempty(tree *t){     return (t->branches == 0) ? 1:0;  }  int isfull(tree *root){     return (root->branches == ((int)pow(2, maxlevel)-1)) ? 1:0; }  tree *copytotree(item *thing){     tree *tmp = initializetree(tmp);      tmp->item = thing;      return tmp;  }  tree **searchtree(tree **t, item *thing, comp f){     int compare;       /*t == null || ..*/      if((*t) == null || (*t)->item == null)         return null;      if((compare = f((*t)->item, thing)) == 0)         return t;      else if(compare > 0)         return searchtree((&((*t)->left)), thing, f);     else         return searchtree((&((*t)->right)), thing, f);  }  int returncount(tree *t){     if(t == null)         return;      t->branches = 1 + returncount(t->left);      t->branches += returncount(t->right);     return t->branches;   }  int addtotree(tree **t, item *thing, comp f){     if(*t == null || (*t)->item == null){         *t = copytotree(thing);         if(*t == null)             return 0;           return 1;      }        if(f((*t)->item, thing) >= 0)         return addtotree(&((*t)->left), thing, f);       else         return addtotree(&((*t)->right), thing, f);  }  int removefromtree(tree **t, item *thing, comp f){     tree **tmp, *tmp2;     if((tmp = searchtree(t, thing, f)) == null)         return 0;     tmp2 = *tmp;       if((*tmp)->left == null ^ (*tmp)->right == null)         ((*tmp)->right == null) ? (*tmp = (*tmp)->left):(*tmp = (*tmp)->right);     else if((*tmp)->left != null && (*tmp)->right != null){         (*tmp) = (*tmp)->left;         /*tmp3 = *tmp;*/         while((*tmp)->right != null)             (*tmp) = (*tmp)->right;          (*tmp) = tmp2->right;      }      free(tmp2->item);     free(tmp2);     return 1;    }  void printtree(tree *t, int level){     if(t == null || t->item == null)         return;       int spaces = 5*(maxlevel - level);      printtree(t->left, level+1);     while(spaces-- > 0)         putchar(' ');      putchar(level + '0');     putchar('\n');       printtree(t->right, level+1);  } 

main.c

/*-------------------------------main.c---------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" #define maxname 20 int itemcomp(const item *, const item *);  int promptuser(void);  item *createuseritem();   int main(){     tree *usertree = initializetree(usertree);       item *useritem;      int userinput;       do{         userinput = promptuser();           switch(userinput){             case 1:                 if((useritem = createuseritem()) && addtotree(&usertree,useritem,itemcomp))                     puts("cat added!");                else                   puts("could not add cat!");                  break;             case 2:                if(useritem = createuseritem()){                   if(removefromtree(&usertree, useritem, itemcomp))                       puts("cat removed!");                 }                else                    puts("could not remove cat!");                 break;              case 3:                 if((useritem =createuseritem()) && searchtree(&usertree,useritem,itemcomp))                    puts("cat found!");                else                    puts("cat not found!");                 break;              case 4:                if(isempty(usertree))                    puts("tree empty!");                else                    puts("tree not empty!");                 break;              case 5:                if(isfull(usertree))                    puts("tree full!");                 else                    puts("tree not full!");                 break;              case 6:                printtree(usertree, 1);                 break;              case 0:                break;             default:                puts("not option!");                 break;         }      }while(userinput);     return 0;   }  int promptuser(){     puts("----------options menu-----------");     puts("1. add cat");      puts("2. remove cat");      puts("3. search cat");      puts("4. check if empty");      puts("5. check if full");      puts("6. print tree");      puts("0. quit");       int userinput = getchar() - '0';      while(getchar() != '\n')         ;     return userinput;  }  item *createuseritem(){     static char namebuf[maxname];      puts("enter cat name: ");      if(fgets(namebuf, maxname, stdin) == null)       return null;       item *tmp = malloc(sizeof(item));      if((tmp->name = malloc(strlen(namebuf))) == null)       return null;       strcpy(tmp->name, namebuf);         tmp->age = -1;      puts("enter cat age");      scanf("%d", &tmp->age);      while(getchar() != '\n')         ;      return tmp; }  int itemcomp(const item *thing_one, const item *thing_two){     int comparison;      if(comparison = strcmp(thing_one->name, thing_two->name)){         printf("the comparison [%d]\n", comparison);          return comparison;      }      return thing_one->age - thing_two->age;  } 

the plan was:

if has no children, free memory tree;

if current tree has 1 child, set current tree's pointer child pointer current tree, because pointer current tree contained within parent of current tree. free memory current tree.

if current tree has 2 children, set current tree's pointer left child pointer current tree (for reasons above), then, traverse left child's right pointers until there's vacancy (null pointer). set current tree's right child vacancy.

any ideas?

i had rebuild remove node function scratch. unfortunately not think had right idea when implementing yourself. removing node tree hard function implement, when managing memory (to avoid memory leaks).

the idea when removing node replace right-most node in left subtree of node want remove. if left subtree empty remove current node entirely , replace right subtree.

it along lines of (not tested -- grasp general idea of this):

// purpose: finds largest node in given tree. once found,  //          returns item , destroys node. // pre: t != null, *t != null // post: - returns pointer item //       - side effect: frees largest node in tree. caller must //                       free returned item. // time: o(n), n height of tree. static item *largestnode( tree **t ) {   assert( t != null );   assert( ( *t ) != null );    if ( ( *t )->right == null ) {     item *key = ( *t )->item;      free( *t );      *t = null;      return key;   } else {     return largestnode( &( ( *t )->right ) );   } }  tree *removefromtree( tree **t, item *key, comp f ) {   // determines whether @ empty node (key not found).   if ( ( t == null ) || ( ( *t ) == null ) )     return null;    // defines temporary tree pointer, tmp , result    // compare function.   tree *tmp = *t;   int const result = f( tmp->item, key );    // determines if result of comparing current node , key    // less. if so, recurse on left subtree. if more, recurse    // on right subtree, otherwise found node want remove,    // remove it.   if ( result < 0 ) {     tmp->left = removefromtree( &( tmp->left ), key, f );   } else if ( result > 0 ) {     tmp->right = removefromtree( &( tmp->right ), key, f );   } else {     // checks if left subtree exists. if not, delete entire current node      // , return right subtree, otherwise left subtree exists ,      // should find largest node in left subtree , replace current      // node item item largest node in left subtree      // delete entirety of largest node in right subtree.     if ( tmp->left == null ) {       tree *tmp_new = tmp->right;        free( tmp );       // @todo: add free item.        return tmp_new;     } else {       item *backup = tmp->item;       tmp->item = largestnode( &( tmp->left ) );        // @todo: add free backup item.        return tmp;     }   } }