Discussion :

[NThierry]

bonjour
je n'arrive pas à rechercher une valeur dans un arbres n-aires
Exple:
typyedef struct Node*tree
struct Node
{
Pelement value;
tree child [4];
}
Aidez moi SVP!

[koala01]

Salut,

L'une des solutions (car il y en a plusieurs sur ce coup) passe par une fonction que l'on appelle "récursive" (qui s'appelle elle-meme).

Je sais bien qu'il existe de nombreuses autres possiblités, mais, du point de vue du code en lui-même, c'est celle qui demande le moins de lignes (sans *forcément* etre la meilleure)

Elle prendrait la forme suivante

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
 
tree SearchInTree(tree ptr, pelement tofind)
{
//un pointeur pour récupérer le résultat
//on l'initialise à NULL par facilité
tree recup=NULL;
//le cas de base: on a trouvé ce qu'on cherche
    if(tofind==ptr->value)
    {
//on modifie recup pour qu'il prenne la valeur de ptr (qui est le noeud recherché)
        recup=ptr;
    }
    else
    {
        //S'il a un  enfant en child[0], on cherche chez cet enfant
        if(child[0]!=NULL)
            recup=SearchInTree(ptr->child[0],tofind);
        //si recup vaut NULL, et qu'il y a un enfant en child[1], on cherche chez lui
        if(child[1]!=NULL && recup!=NULL)
             recup=SearchInTree(ptr->child[1],tofind);
        //si recup vaut encore NULL, et qu'il y a un enfant en child[2], on cherche chez lui
        if(child[2]!=NULL && recup!=NULL)
            recup=SearchInTree(ptr->child[2],tofind);
        //si recup vaut toujours NULL, et qu'il y a un enfant en child[3], on cherche chez lui
        if(child[3]!=NULL && recup!=NULL)
            recup=SearchInTree(ptr->child[3],tofind);               
    }
//au final, on renvoie recup...
    return recup;
}

En n'oubliant quand meme pas d'adapter le test du cas de base au type de valeur que représente value

Beaucoup me diront, a juste titre, qu'il est préférable de créer ses tests de manière à ce que la plus grande partie du travail se fasse dans la partie "vrai"...

A titre tout à fait personnel et dans le cas exceptionnel que représente un fonction récursive, je préfere largement etre sur que le cas de base est bel et bien vérifié, car sinon des catastrophes peuvent arriver

[fearyourself]

En reprenant le code de koala, je généraliserais quand même un peu...

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
tree SearchInTree(tree ptr, pelement tofind)
{
int i;
//un pointeur pour récupérer le résultat
//on l'initialise à NULL par facilité
tree recup=NULL;
//le cas de base: on a trouvé ce qu'on cherche
    if(macomparaison(tofind,ptr->value) == 0)
    {
//on modifie recup pour qu'il prenne la valeur de ptr (qui est le noeud recherché)
        recup=ptr;
    }
    else
    {
        for(i=0;i<4;i++)
          {
          if(child[i]!=NULL) 
              {
              recup = SearchInTree(ptr->child[i],tofind);
 
              if(recup) 
                 {
                  //On sort
                  break;
                  }
              }
          }
    }
    //au final, on renvoie recup...
    return recup;
}

Je suppose par contre que pelement est un pointeur... Remarque l'utilisation de la fonction macomparaison permet de faire une comparaison avec un == (donc on regarde la valeur du pointeur) ou une comparaison de ce qui se trouve dans la zone pointée...

Jc

[koala01]

C'est pourquoi, quitte à faire quelque chose en boucle, j'utiliserais plutot une boucle while()

En reprenant le code, ca deviendrait

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
 
tree SearchInTree(tree ptr, pelement tofind)
{
int i;
//un pointeur pour récupérer le résultat
//on l'initialise à NULL par facilité
tree recup=NULL;
//le cas de base: on a trouvé ce qu'on cherche
    if(macomparaison(tofind,ptr->value) == 0)
    {
//on modifie recup pour qu'il prenne la valeur de ptr (qui est le noeud recherché)
        recup=ptr;
    }
    else
    {
        i=0;
        while(i<4 && recup==NULL)
        {
            recup = SearchInTree(ptr->child[i],tofind);
            i++;
        }
    }
    //au final, on renvoie recup...
    return recup;
}

Je sais que ca revient quasiment au meme, mais, je n'aime vraiment pas les break quand je peux m'en passer... Mais ca, ce n'est que mon avis personnel...

Si, maintenant, quelqu'un peut m'assurer que ta manière est préférable du point de vue des performances, il n'est pas exclu que je me réconcilie d'avec eux

Nota: contrairement à mon habitude en situation réelle, je n'avais fait aucun algorithme pour mon premier code

Edit==> je reconnais là que je chipote quelque peu...