Segmentation fault in binary tree implementation

Question

I apologize in advance for how long the source code on this one is. I'm not entirely sure where I'm going wrong here. I wrote a binary tree implementation and some functions for tree traversal. Adding one item to the tree works, but adding multiple causes a segmentation fault. DDD lists several functions in the backtrace: isfull, addToTree, and isEmpty are named.

The program spans three source files (sorry).

/*----------------------------------Tree.h----------------------------------*/

#ifndef TREE
#define TREE

#define MAXHEIGHT 4

typedef struct cat{
    char *name; 
    int age; 
}Item; 

typedef struct node{
    Item thing; 
}Node; 

typedef struct tree{
    Node *root;
    struct tree *left, *right;  
    int leafcount; 
}Tree; 

void initializeTree(Tree *); 
void closeTree(Tree *); 
int isEmpty(const Tree *);
int isFull(const Tree*); 
Tree *searchTree(Item *thing, Tree *t, int (*)(const Item *, const Item *)); 
int addToTree(Item *, Tree *, int (*)(const Item *, const Item *)); 
int removeFromTree(Item *, Tree *);

int itemComp(const Item *, const Item *); 

#endif

/*----------------------------------Tree.c----------------------------------*/

#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

Node *copyToNode(Item *); 

/*Definition: Tree
  Node *root; 
  int leafcount; */

Node *copyToNode(Item *thing){
    Node *tmp = malloc(sizeof(Node)); 
    if(tmp == NULL)
        return tmp; 
    tmp->thing = *thing; 
    return tmp; 
}

void initializeTree(Tree *t){
    t->root = NULL; 
    t->right = t->left = NULL; 
    t->leafcount = 0; 
}

int isEmpty(const Tree *t){
    return t->root == NULL; 
}

int isFull(const Tree *t){
    return t->leafcount == (int)pow(2,MAXHEIGHT) - 1;  
} 

int addToTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){
    if(isFull(t))
        return 0;

    if(isEmpty(t)){
        Node *current = copyToNode(thing);
        if(current == NULL){
            puts("Couldn't copy to tree!");
            return 0; 
        } 
        t->root = current;
        t->leafcount++; 
        return 1; 
    } 

    if(fp(thing, &t->root->thing) <= 0)
       return addToTree(thing, t->left, fp); 
    else
       return addToTree(thing, t->right, fp);  
}

Tree *searchTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){
    int temp; 

    if(t->root == NULL) 
        return NULL; 
    else if((temp = fp(&t->root->thing, thing)) == 0)
        return t;
    else if(temp = -1)
        return searchTree(thing, t->left, fp);
    else
        return searchTree(thing, t->right, fp);  
}


int removeFromTree(Item *thing, Tree *t){
    /*Tree *tmp = searchTree(thing, t); 
    Not finished*/ 
}

void closeTree(Tree *t){
    return; 
}

    /*------------------------------TreeDriver.c-------------------------------*/
#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNAME 30 
int promptUser(void); 
int itemComp(const Item *, const Item *);
Item * createUserItem(); 

int main(){
    int userChoice;
    Item * userItem = NULL; 
    Tree userTree; 

    initializeTree(&userTree); 

    do{
        userChoice = promptUser();
        switch(userChoice){
            case 1:
                puts("Enter cat information to add"); 
                userItem = createUserItem(); 
                if(addToTree(userItem, &userTree, itemComp))
                    puts("Cat successfully added!"); 
                else
                    puts("Could not add cat!"); 
                break;
            case 2:
                puts("Enter cat information to search for"); 
                userItem = createUserItem();
                if(searchTree(userItem, &userTree, itemComp))
                   puts("Cat found!");
                else
                   puts("Cat not found!"); 
                break; 
            case 3:
                if(isEmpty(&userTree))
                    puts("Tree is empty!");
                else
                    puts("Tree is not empty!");
                break;
            case 4:
                if(isFull(&userTree))
                    puts("Tree is full!");
                else
                    puts("Tree is not full!"); 
                break;
            case 0:
                break;
            default:
                puts("Not an option!"); 
                break;
        }

    }while(userChoice); 

}

int itemComp(const Item *thing_one, const Item *thing_two){
    int comparison;

    if(comparison = strcmp(thing_one->name, thing_two->name))
        return comparison; 

    return !(thing_one->age == thing_two->age);
}

int promptUser(){
    int tmp; 

    puts("--------MENU---------");
    puts("1. Create cat"); 
    puts("2. Search for cat"); 
    puts("3. Check empty");
    puts("4. Check full"); 
    puts("0. Quit"); 

    scanf("%d", &tmp); 
    while(getchar() != '\n')
        ;

    return tmp; 
}

Item * createUserItem(){
    Item *tmp = malloc(sizeof(Item));  
    static char namebuf[MAXNAME];

    printf("Enter cat name: "); 
    if(fgets(namebuf, MAXNAME, stdin) == NULL)
        return NULL; 

    tmp->name = malloc(strlen(namebuf)); 
    strcpy(tmp->name, namebuf);

    printf("Enter cat age:\t");
    scanf("%d", &tmp->age); 

    while(getchar() != '\n')
       ;

    return tmp; 
}

I'm not exactly sure how to interpret a debugger's backtrace anyway. Where did I go wrong? Could it have something to do with how I handled creating a dummy Item for user input in the driver file? I don't think I handled that (or the rest of this program for that matter) very well.

Thanks

Your addToTree function should not even work... you would need to use a double pointer to a struct tree. — Jacob Pollack
– Jacob Pollack, Commented Aug 14, 2013 at 1:32

Jacob Pollack · Accepted Answer · 2013-08-14 01:49:36Z

Disclaimer: Since you specified that you think the error lies within your addToTree function I did not look anywhere else for errors (other than your structure definitions).

You have two errors in your addToTree function. The first being, you are not handling the leafcount correctly. You will find that it is incorrect as you push nodes into your tree (my solution below does not fix that). Secondly, you need to pass a double pointer to a struct tree (or Tree), passing a single pointer will not let you insert into an empty tree since you would be passing NULL.

The only reason the first insert works and the proceeding ones do not is because you have already created a node (whereas if you used a wrapper structure it should be NULL).

To fix the second error, do the following:

int addToTree( Item *thing, Tree **t, int ( *fp )( const Item *, const Item * ) ) {
    if( isFull( *t ) == true) return 0;

    if( isEmpty( *t ) == true ) {
        Node *current = copyToNode( thing );

        if( current == NULL ) {
            puts( "Couldn't copy to tree!" );

            return 0; 
        }

        ( *t ) = current;

        return 1; 
    } 

    if( fp( thing, t->root->thing ) <= 0 )
       return addToTree( thing, &( ( *t )->left ), fp ); 
    else
       return addToTree( thing, &( ( *t )->right ), fp );  
}

Aside: I would also consider naming your structures differently. The structure Node and Tree are misleading, Node should become Item and Tree should become BstNode (or any naming scheme you see fit along the lines of that), then have a wrapper structure called BstTree that is defined as follows:

struct BstTree {
  struct Tree *root;
  int height;
};

... where root points to the root Node and height is the height of the Binary Search Tree. This will not only communicate better your intentions but make your implementation much easier to work with.

Collectives™ on Stack Overflow

Segmentation fault in binary tree implementation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related