Discussion :

[wolflinger]

Bonjour,

Je fais un programme qui utilise des arbres binaire de recherche mais la dernière fonction me pose problème. Elle doit supprimer le noeud ou la feuille recherché(e).

Voici ma struture d'arbre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
typedef struct snoeud{
  int valeur;
  struct snoeud *fg;
  struct snoeud *fd;
} noeud;
 
typedef noeud * arbre;

Voici la fonction telle qu'elle est en ce moment :
(je l'ai déjà modifiée dans tous les sens mais c'est la version qui me donne les résultats les plus correctes)

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
void supprimerElement(arbre *a, int val){
  if( (*a)->valeur == val )
    {
      if( (*a)->fg )
	{
	  (*a) = (*a)->fg;
	  while( (*a)->fd )
	    {
	      (*a) = (*a)->fd;
	    }
	  (*a)->fd = (*a)->fd;
	  (*a) = (*a)->fg;
	}
      else
	{
	  (*a) = (*a)->fd;
	 }
    }
  else
    {
      if( val < (*a)->valeur )
	{
	  supprimerElement( &(*a)->fg, val);
	}
      else
	{
	  supprimerElement( &(*a)->fd, val);
	}
    }
}

Je sais qu'il manque des tests mais je n'arrive pas à les implémenter correctement...

Si vous avez un conseil à me donner je suis preneur
Merci d'avance!

A bientôt

[wolflinger]

Re'

je viens d'avoir une idée : la création d'une nouvelle fonction pour replacer correctement un fils d'un noeud.

voici ce que ca donne :

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
void supprimerElement(arbre *a, int val){
  if( *a == NULL ) printf("Rien a supprimer\n");
  if( (*a)->valeur == val )
    {
      if( (*a)->fg == NULL ) (*a) = (*a)->fd;
      else
	if ( (*a)->fd == NULL ) (*a) = (*a)->fg;
	else
	  replacerFils( &(*a)->fg );
    }
  else
    {
      if( val < (*a)->valeur )
	{
	  supprimerElement( &(*a)->fg, val);
	}
      else
	{
	  supprimerElement( &(*a)->fd, val);
	}
    }
}
 
void replacerFils( arbre *a){
  if( (*a)->fd == NULL )
    (*a) = (*a)->fg;
  else
    replacerFils( &(*a)->fg );
}

je n'ai plus d'erreur mais les résultats sont parfois faux pour des noeuds à 2 fils

[Trap D]

Moi je ferais comme celà :
J'ai supposé, d'après ce qui est écrit, que arbre est un pointeur vers une structure

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
33
34
arbre supprimerElement(arbre a, int val)
{
    arbre tmp;
    if( (a->valeur == val )
    {
       if( a->fg != NULL)
       {
          // on accroche a->fd au fils le plus à droite du fils gauche 
          tmp = a->fg;
          while(tmp->fd != NULL)
          {
             tmp = tmp->fd;
          }
          tmp->fd = a->fd;
          a = a->fg;
       }
       else
       {
           a = a->fd;
       }
    }
    else
    {
        if( val < a->valeur )
        {
            a->fg = supprimerElement( a->fg, val);
        }
        else
        {
            a->fd = supprimerElement( a->fd, val);
        }
    }
    return a;
}

PS : il y a peut-être lieu de libérer le noeud lorsque val = a ->valeur.

[wolflinger]

merci beaucoup Trap D!

j'avais déjà essayé en utilisant un arbre temporaire mais je me compliquais bien et n'arrivais jamais au bon résultat.
de plus j'étais persuadé que c'était possible sans mais finalement je pense que non

encore merci
@bientôt

PS : désolé du retard, vacance oblige j'avais oublié ceci 8)