nono1307
Messages postés3Date d'inscriptionmercredi 28 avril 2004StatutMembreDernière intervention18 novembre 2004
-
28 avril 2004 à 12:14
nono1307
Messages postés3Date d'inscriptionmercredi 28 avril 2004StatutMembreDernière intervention18 novembre 2004
-
28 avril 2004 à 12:14
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
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