problem in creating binary search tree in c language

Question

This code creates a binary search tree but it runs sometimes normally and sometimes makes errors, even without changing anything in the code.

I can't get why this happening, what's the mistake ?

Even I changed the function that I used to create the tree from recursive to iterative but the same results.

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

typedef struct sommet{
    struct sommet * fg;
    int val;
    struct sommet * fd;
}sommet;
typedef sommet* ptrm;

ptrm creearbre(ptrm arbre,int ele);
void impression(ptrm arbre);
ptrm creearbre_rec(ptrm arbre,int ele);

int main()
{
        ptrm arbre=NULL;
        int tarbre,n;
        printf("entre la taille de l'arbre:");
        scanf("%d",&tarbre);
        for(int i=0;i<tarbre;i++)
        {
            printf("entre l'element %d: ",i+1);
            scanf("%d",&n);
            arbre=creearbre_rec(arbre,n);
        }
        impression(arbre);
    return 0;
}

ptrm creearbre_rec(ptrm arbre,int ele)
{
    if(arbre==NULL)
    {
        arbre=malloc(sizeof arbre);
        arbre->val=ele;
        arbre->fd=NULL;
        arbre->fg=NULL;
    }
    else if(arbre->val > ele)
        arbre->fg=creearbre_rec(arbre->fg,ele);
    else
        arbre->fd=creearbre_rec(arbre->fd,ele);
return arbre;
}

void impression(ptrm arbre){
        if(arbre != NULL){
        printf(" %d -->", arbre->val);
        impression(arbre->fg);
        impression(arbre->fd);
    }
}


ptrm creearbre(ptrm arbre,int ele){
    ptrm p,q=arbre,r=NULL;
    p=malloc(sizeof arbre);
    p->val=ele;
    p->fd=NULL;
    p->fg=NULL;
    if(arbre==NULL){
        arbre=p;
    }
    else{
        while(q!=NULL){
            r=q;
            if(ele > q->val)
                q=q->fd;
            else
                q=q->fg;
        }
        if(ele > r->val)
            r->fd=p;
        else
            r->fg=p;
    }
    return arbre;
}

Welcome to Stack Overflow. "makes errors" is not a very useful description. Please give the exact errors. Usually by providing the exact input, expected result and actual result. — kaylum
– kaylum, Commented Jan 24, 2022 at 11:17
Don't typedef pointers. It just makes it confusing for yourself and others. It could be one reason why you do things like this which are wrong: malloc(sizeof arbre);. That should be malloc(sizeof *arbre); — kaylum
– kaylum, Commented Jan 24, 2022 at 11:20
Second that. do NOT hide pointer types in aliases. It proffers absolutely zero clarity to the code when used incorrectly (e.g all cases but two: "handle"-based blackbox APIs, and callback function types, neither of which are applicable to you). C programmers want to "see the splats". They're the visual calling card that proclaim "this is a pointer". Don't fight that; embrace it. — WhozCraig
– WhozCraig, Commented Jan 24, 2022 at 11:20
Please edit and add an example of input that produces "Errors" (whatever that is). — Jabberwocky
– Jabberwocky, Commented Jan 24, 2022 at 11:28
Your chances for help will increase when you spend the effort of doing SO best practices, because they will either help you directly or will improve other users willlingness to help. a) do not hide pointers b) do not ignore scanf return values c) apply consistent indentation d) init all variables (if you are sure that they will be written to beofre being read the please still init them with very recognisable values e) translate everything to English — Yunnosch
– Yunnosch, Commented Jan 24, 2022 at 11:35

Vlad from Moscow · Accepted Answer · 2022-01-24 12:30:08Z

1

The program has undefined behavior due to using an invalid size in the allocation of memory in statements

arbre=malloc(sizeof arbre);

and

p=malloc(sizeof arbre);

There are allocated memory for pointers instead of objects of the structure type.

You need to write

arbre=malloc(sizeof *arbre);

p=malloc(sizeof *arbre);

edited Jan 24, 2022 at 12:30

answered Jan 24, 2022 at 11:32

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

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

2 Comments

Yunnosch Over a year ago

If this is thes solution then it is a perfect example of why not to hide pointers. :-)

Houssam Eddine Over a year ago

@Yunnosch yes it's the right answer, i won't typedef pointers anymore

Collectives™ on Stack Overflow

problem in creating binary search tree in c language

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related