inserting node (Binary search tree) C

Question

I'm trying to insert a node in a binary search tree and I'm getting a little problem.

#include "stdafx.h"
#include <string.h>
#include <stdlib.h>


typedef struct Node{
    char name[100];
    struct Node *pGauche;
    struct Node *pDroit;
}Node;

void getName(char[]);
void copy(Node **, Node *,char[]);
void menu(Node **);
void add(Node **);
void search(char[],Node**, Node **,Node **);
void print(Node **);
void inOrder(Node *);

void main(void)
{
    Node *root = NULL;
    menu(&root);
    system("pause");
}

void menu(Node **root)
{
    for (int i=0;i<10;i++)
    {
        add(root);
    }
    print(root);
}

void add(Node **root)
{
    char name[100];
    getName(name);
    Node *p = NULL;
    Node *savep = NULL;
    search(name,root,&p,&savep);
    copy(root,savep,name);
}

void search(char name[],Node **root, Node **p, Node **savep)
{
    *p = *root;

    while ((p == NULL) && (strcmp((*p)->name,name) != 0))
    {
        *savep = *p;

        if (strcmp(name,(*p)->name) < 0)
            *p = (*p)->pGauche;
        else
            *p = (*p)->pDroit;
    }

}

void getName(char name[])
{
    printf("What name do you want to add\n");
    scanf("%s",name);
    fflush(stdin);

}

void copy(Node **root, Node *savep, char name[])
{
    Node *newp = (Node *) malloc(sizeof(Node*));
    newp->pDroit = NULL;
    newp->pGauche = NULL;

    strcpy(newp->name,name);
    printf("%s",newp->name);


    if (*root == NULL)
        *root = newp;
    else
    {
        if (strcmp(name,savep->name) < 0) 
            savep->pGauche = newp;
        else
            savep->pDroit = newp;
    }
    free(newp);
}

void print(Node ** root)
{
    Node *p = *root;
    inOrder(p);
}

void inOrder(Node *p)
{
    if (p != NULL)
    {
        inOrder(p->pGauche);
        printf("%s\n",p->name);
        inOrder(p->pDroit);
    }
}

I know there are some really odd function and useless functions, but this just a "test" for a slightly bigger school project so it will get useful in time, right now I would just like to get the binary tree working !

So basically the problem is that I'm getting a "Access violation reading location" after I type in the second name... I'm guessing when doing the strcmp, but I'm really not sure :/

I'd really be glad if someone could help me getting this running :)

You should try running your code in a debugger to understand better why the code is crashing. — jxh
– jxh, Commented May 10, 2013 at 21:55

jxh · Accepted Answer · 2013-05-10 22:47:01Z

3

A couple of things to get you started. I haven't looked into it too deeply, so you will probably have to continue to drill down into more issues, but fix these things just to get you started:

In this code in search():

    while ((p == NULL) && (strcmp((*p)->name,name) != 0))

The p parameter will never be NULL. So, the while loop is never entered. This means that savep would not get set to any value, and is NULL when you call copy() in your add() function. The copy() function then dereferences the invalid pointer reference, which caused the problem you observed.

You actually want to test to see if *p is NOT NULL. This allows you to legally dereference it.

    while ((*p != NULL) && (strcmp((*p)->name,name) != 0))

Secondly, as hmjd identified, you do not allocate enough memory for your node inside copy().

    Node *newp = (Node *) malloc(sizeof(Node*));

You are only allocating enough memory for one pointer, not for an entire node. Also, you should not cast the return value of malloc() when coding in C (it will hide a bug that can lead to a crash in the worst case).

    Node *newp = malloc(sizeof(Node));

Thirdly, you need to retain the memory you allocate for your nodes rather than freeing them immediately after inserting it at the end of copy():

    // I need this memory for my tree!
    //free(newp);

If you call free() like you did, then your tree will be pointing into freed memory, and to access them would cause undefined behavior.

One minor thing: You shouldn't do fflush(stdin), as fflush() is only for output streams.

edited May 10, 2013 at 22:47

answered May 10, 2013 at 22:13

jxh

70.8k8 gold badges116 silver badges204 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

hmjd Over a year ago

And one for you. There are many bugs in the code as you have identified. There may be others but the OP can at least fix those listed and hopefully learn something. Enabling him/her to fix other bugs unmentioned in the answers.

Zoé de Moffarts Over a year ago

Thanks a lot to you two guys, that was indeed very helpful and helped me learn from the mistakes I made :D Everything is running smooth now !

hmjd · Accepted Answer · 2013-05-10 22:23:27Z

3

This is incorrect:

while ((p == NULL) && (strcmp((*p)->name,name) != 0))

and will result in a NULL pointer being dereferenced, which is undefined behaviour. Change to:

while (*p && strcmp((*p)->name,name) != 0)

This is incorrect:

Node *newp = (Node *) malloc(sizeof(Node*));

as it is only allocating enough for a Node*, when it needs to be allocating a Node. Change to:

Node *newp = malloc(sizeof(*newp));

and don't free() it in the same function as it is required later. free()ing the Node means the list has dangling pointers and dereferencing one is undefined behaviour, and a probable cause of the access violation.

Note:

fflush(stdin);

is undefined behaviour. From the fflush() reference page:

Causes the output file stream to be synchronized with the actual contents of the file. If the given stream is of the input type, then the behavior of the function is undefined.

edited May 10, 2013 at 22:23

answered May 10, 2013 at 22:11

hmjd

122k21 gold badges216 silver badges259 bronze badges

3 Comments

jxh Over a year ago

Your analysis of what caused the asker's problem is incomplete.

hmjd Over a year ago

@user315052, ok but it will help at least.

jxh Over a year ago

Yes, that's why I have +1'd you.

Collectives™ on Stack Overflow

inserting node (Binary search tree) C

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related