CODEWITHSUNDEEP
csegmentation-faultbinary-tree
user3423880
user3423880

Reputation: 33

C segmentation fault in insert to binary tree

I am still very new to C, and am trying to figure out why I (believe) that I am getting a segmentation fault. I say believe, because the exe stops working, and so I just try and run it in Eclipse's debugger, and that's where I see the error happening. Any help/suggestions/criticisms are highly welcomed.

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
struct node *left;
struct node *right;
double key;
} node;

void addNode(double value, node **node);
double dRand();
//node* search(double value, node *root);
void killTree(node *root);

int main(void)
{
    int nodesToAdd, i;
    node *n = NULL;
    node **p = &n;
    nodesToAdd = 10;
    for(i=0;i<nodesToAdd;i++)
    {
        printf("DEBUG: Adding node %d to tree\n", i+1);
        addNode(dRand(), p);
    }
    printf("DEBUG: Finished creating tree\n");
    printf("DEBUG: Freeing memory of tree\n");
    killTree(n);
    return 0;
}


double dRand()
{
return ((double)rand()/RAND_MAX)*10;
}

void addNode(double value, node **tree)
{
    node *insert = malloc(sizeof(*insert));
    insert->key = value;


    while(*tree){
        if(value < (*tree)->key)    tree = &(*tree)->left;
        else if(value > (*tree)->key) tree = &(*tree)->right;
        else return;
    }
    *tree = insert;
}

void killTree(node *node)
{
    if(!node){}
    else
    {
        killTree(node->left);
        killTree(node->right);
        printf("DEBUG: Deleting pointer to node of value %f from mem\n", node->key);
        free(node);
    }
}

EDIT: I think that the error comes from trying to reference the right and left nodes before they are allocated memory, but I'm not sure what it is that I am doing wrong.

EDIT2:Thanks so much, that worked wonderfully!

Upvotes: 3

Views: 402

Answers (1)

WhozCraig
WhozCraig

Reputation: 66254

You have a memory leak in your addNode function if a match is found. You allocate, then search. You should search, then allocate only if the search failed.

Regarding your crash, you're not initializing a new node's left and right pointers to NULL. This is critical. The next time you enter the tree to chase down a search, you will dereference indeterminate pointers, and invoke undefined behavior as a result.

Perhaps something like this:

void addNode(double value, node **tree)
{
    // search first
    while (*tree)
    {
        if (value < (*tree)->key) 
            tree = &(*tree)->left;
        else if((*tree)->key < value) 
            tree = &(*tree)->right;
        else return;
    }

    // no match, so add
    *tree = malloc(sizeof(**tree));
    (*tree)->key = value;
    (*tree)->left = (*tree)->right = NULL; // note: set to null
}

Next, though not critical, your main() function has no need for p. You can use your node pointer by-address directly:

int main(void)
{
    int nodesToAdd, i;
    node *n = NULL;

    nodesToAdd = 10;
    for(i=0;i<nodesToAdd;i++)
    {
        printf("DEBUG: Adding node %d to tree\n", i+1);
        addNode(dRand(), &n);
    }
    printf("DEBUG: Finished creating tree\n");
    printf("DEBUG: Freeing memory of tree\n");
    killTree(n);
    return 0;
}

And for what it's worth, if your new to C, this isn't terrible. Grasping double-indirection is a common stall-point in the C learning curve, and your use in your add function wasn't terrible at all. Keep at it.

Upvotes: 3

Related Questions