Probleme avec mon programme en C

Je dois faire une fonction insertion dans un arbre ternaire.

Voici ce que j'ai fait :

#include <stdio.h> #include <stdlib.h> #include "arbre-2-3.h" #include "pile.h" //************************************** //* Nom de la fonction: gauche * //* Retourne l'arbre situe a la gauche * //* De l'arbre courant * //* Entree: l'Arbre_2_3 pere * //* Sortie: l'Arbre2_3 de gauche * //************************************** Arbre_2_3 gauche(Arbre_2_3 a) { return a->fg; } //************************************** //* Nom de la fonction: milieu * //* Retourne l'arbre situe au milieu * //* De l'arbre courant * //* Entree: l'Arbre_2_3 pere * //* Sortie: l'Arbre2_3 du milieu * //************************************** Arbre_2_3 milieu(Arbre_2_3 a) { return a->fm; } //************************************** //* Nom de la fonction: droit * //* Retourne l'arbre situe a la droite * //* De l'arbre courant * //* Entree: l'Arbre_2_3 pere * //* Sortie: l'Arbre2_3 de droite * //************************************** Arbre_2_3 droit(Arbre_2_3 a) { return a->fd; } //************************************** //* Nom de la fonction: val_g * //* Retourne la valeur gauche du noeud * //* Courant * //* Entree: l'Arbre_2_3 pere * //* Sortie: valeur de gauche * //************************************** element val_g(Arbre_2_3 a) { return a->vg; } //************************************** //* Nom de la fonction: val_d * //* Retourne la valeur gauche du noeud * //* Courant * //* Entree: l'Arbre_2_3 pere * //* Sortie: valeur de droite * //************************************** element val_d(Arbre_2_3 a) { return a->vd; } //************************************** //* Nom de la fonction: est2_noeud * //* Tester si le noeud est un 2_noeud * //* Entree: l'Arbre2_3 courant * //* Sortie: 1 si c'est un 2_noeud * //* 0 autrement * //************************************** int est2_noeud (Arbre_2_3 a) { if (val_d(a)==Rien) return 1; else return 0; } //************************************** //* Nom de la fonction: creer_noeud * //* Cree un noeud * //* Entree: rien * //* Sortie : un nouveau noeud * //************************************** Arbre_2_3 creer_noeud() { Arbre_2_3 a=(Arbre_2_3)malloc(sizeof(Cellule_a)); a->vg=Rien; a->vd=Rien; a->fg=Arbre_Vide; a->fm=Arbre_Vide; a->fd=Arbre_Vide; return a; } //************************************** //* Nom de la fonction: appartient * //* Tester si l'element en parametre * //* existe dans l'arbre * //* Entree: l'Arbre_2_3 courant et * //* l'element a rechercher * //* Sortie: 1 si l'element existe deja * //* 0 autrement * //************************************** int appartient(element X, Arbre_2_3 a) { if (vide(a)) return 0; else if ((X==val_g(a)) || (X==val_d(a))) return 1; else if(X<val_g(a)) return appartient(X,gauche(a)); else if (X>val_d(a)) return appartient(X,droit(a)); else return appartient(X,milieu(a)); } //************************************** //* Nom de la fonction: insertion * //* Insere l'element en parametre dans * //* l'arbre * //* Entree: l'element a inserer et un * //* pointeur sur l'arbre * //* Sortie: rien * //************************************** void insertion(element X, Arbre_2_3 *a) { int sens; Arbre_2_3 temp,A,noeud_inf,noeud_med,noeud_sup; temp=*a; A=creer_noeud(); A->vg=X; Pile p=Pile_Vide; /* if(appartient(X,*a)) { erreur("la valeur est deja present dans l'arbre !!!"); }*/ // else { while(!vide(temp)) { if(X<val_g(temp)) { p=empiler2(temp,-1,p); temp=gauche(temp); } else { if(X>val_d(temp)) { p=empiler2(temp,1,p); temp=droit(temp); } else { p=empiler2(temp,0,p); temp=milieu(temp); } } } while ((!vide(p)) && (!est2_noeud((sommet(p))))) { sens=sommet2(p); temp=extraire(&p); noeud_inf=creer_noeud(); noeud_med=creer_noeud(); noeud_sup=creer_noeud(); noeud_med->fg=noeud_inf; noeud_med->fm=noeud_sup; if(sens==0) //on vient du milieu { noeud_inf->vg=temp->vg; noeud_med->vg=A->vg; noeud_sup->vg=temp->vd; noeud_inf->fg=(temp)->fg; noeud_inf->fm=A->fg; noeud_sup->fg=A->fm; noeud_sup->fm=(temp)->fd; } else { if (sens==1) //on vient de droite { noeud_inf->vg=temp->vg; noeud_med->vg=temp->vg; noeud_sup->vg=A->vd; noeud_inf->fm=temp->fm; noeud_inf->fg=temp->fg; } else { // on vient de gauche noeud_inf->vg=A->vg; noeud_med->vg=temp->vg; noeud_sup->vg=temp->vd; noeud_sup->fg=(temp)->fm; noeud_sup->fm=(temp)->fd; } } A->vg=noeud_med->vg; A=noeud_med; } if (vide(p)) // on a un arbre vide { *a=A; } else //on a un 2_noeuds { if (sommet2(p)==0) // on vient du milieu { temp=extraire(&p); temp->vd=A->vg; temp->fd=A->fm; temp->fm=A->fg; } else { // on vient de gauche temp=extraire(&p); temp->vd=temp->vg; temp->vg=A->vg; temp->fg=A->fg; temp->fd=temp->fm; temp->fm=A->fm; } } } void suppression(element n, Arbre_2_3 *a) { } void detruire_arbre(Arbre_2_3 a) { if(!vide(a)) { detruire_arbre(gauche(a)); detruire_arbre(droit(a)); free(a); } } void detruire_pile(Pile p) { if(!vide(&p)) { p=depiler(p); } free(p); }

Les .h :

//****************************************************************************** //* * //* * //* * //* **************************************************** * //* * * * //* * * * //* * ARBRES TERNAIRES EQUILIBRES * * //* * * * //* * * * //* **************************************************** * //* * Projet Filiere Elec 2004 * * //* **************************************************** * //* * * * //* **************************************************** * //* * Interface de : Arbre * * //* **************************************************** * //* * //* * //* * //****************************************************************************** #ifndef _ARBRE_ #define _ARBRE_ #include <limits.h> #include <stdlib.h> typedef int element; typedef struct Cellule_a { element vd,vg; struct Cellule_a * fg,*fm,*fd; } Cellule_a,* Arbre_2_3; #define Rien INT_MAX #define Arbre_Vide NULL /* Convention | lorsqu'un noeud N est un 2-noeud, la valeur de N.vg */ /* | est : Rien , la valeur de N.fd est : Arbre_Vide */ int vide (void *); element val_g (Arbre_2_3); element val_d (Arbre_2_3); Arbre_2_3 gauche (Arbre_2_3); Arbre_2_3 milieu (Arbre_2_3); Arbre_2_3 droit (Arbre_2_3); int estderniernoeud (Arbre_2_3); int est2_noeud (Arbre_2_3); int appartient (element, Arbre_2_3 ); void insertion (element, Arbre_2_3 * ); void suppression(element, Arbre_2_3 * ); extern void erreur (char*); #endif

#ifndef _PILE_ #define _PILE_ #include "arbre-2-3.h" #define Pile_Vide NULL typedef enum {a_gauche=-1,au_milieu=0, a_droite=1} Sens; typedef struct Cellule_p { Arbre_2_3 val; Sens sens; struct Cellule_p * next; } Cellule_p,* Pile; int vide (void * p); Arbre_2_3 sommet(Pile ); Sens sommet2( Pile P); Pile empiler( Arbre_2_3 ,Pile ); Pile empiler2(Arbre_2_3 ,Sens , Pile ); Pile depiler(Pile ); void vider (Pile *) ; Arbre_2_3 extraire(Pile *); #endif

Le probleme vient de la boucle while ((!vide(p)) && (!est2_noeud((sommet(p)))))
J'ai mis un printf dedans , et lorsqu'on doit normalement entrer dans cette boucle, on y rentre pas.

Quand j'execute le programme, il y a un premier noeud qui se créé (c'est un 2-noeud). Je rajoute une valeur, ca marche , le noeud devient alors un 3-noeud. Mais le probleme vient quand je veux insérer une troisieme valeur. Normalement, on doit casser le 3-noeud en 2 2-noeud. Puis faire un traitement afin de faire remonter la valeur mediane.
On doit avoir un 2-noeud contenant la valeur mediane qui pointe sur un 2-noeud ayant la valeur la plus petite et sur un 2-noeud ayant la valeur supérieure.

Bref, ca ne marche pas! Franchement, je ne vois ou ca bug

Pour info, je compile sous gcc

Je vous remercie d'avance