Bonjour

Le critere d’ ́equilibre est la taille des sous-arbres : un arbre est equilibre si, pour tout noeud de l’arbre, la taille de son fils gauche est egale a la taille de son fils droit a` un noeud pr`es (la taille d’un arbre est son nombre de noeuds, feuilles comprises).

Ecrire en C la fonction ConstruitArbreEquilibre(int T[], int g, int d) qui construit et renvoie un arbre binaire de recherche equilibre contenant les valeurs T[g], T[g+1],..., T[d]. On suppose que les valeurs dans le tableau T sont definies pour les indices compris entre g et d, et sont ordonnees dans l’ordre croissant.

Bref j'ai pensé a faire une dichotomie sur le tableau a chaque fois ajouté l'élement médian, mais j'arrive pas à l'implémenter avec ce protoype.
Voici mon code :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef struct noeud* ARBRE;
 
typedef struct noeud
{
    int val;
    struct noeud* fg;
    struct noeud* fd;
} NOEUD;
 
ARBRE cree_Noeud(int val, ARBRE fg, ARBRE fd)
{
    ARBRE arbre = malloc(sizeof(struct noeud));
    arbre->val = val;
    arbre->fg = fg;
    arbre->fd = fd;
    return arbre;
}
 
ARBRE inserer(int val,ARBRE a)
{
    if(a == NULL)
            return cree_Noeud(val,NULL,NULL);
    if(val < a->val)
            a->fg=inserer(val,a->fg);
    else if(val > a->val) 
    			a->fd = inserer(val,a->fd);
    return a;
}
ConstruitArbreEquilibre(int T[], int g, int d)
{
 
}
J'ai vraiment du mal :/ si vous pouvez m'aider.Bonne année =)