Discussion :

[wedoud]

slt tout le monde
je veux savoir une strategie recursive pour regler un probléme sur ma fonction qui prend en paramétre l'adresse memoire de la racine d'un arbre AVL
et l'adresse memoire d'un noeud x de ce même arbre et qui retourne l'adresse-mémoire du noued suivant x dans l'orde "priorite au pére"
le modele d'imlantation d'un noeud typique de l'arbre AVL est le suivant :
typedef struct noeud
{
int valeur ;
struct noeud *gauche ,*droite;
}Noeud ;
typedef Noeud*Arbre;
prototype de la fonction est:
Arbre suivant(Arbre racine;Arbre x)
{}

[fearyourself]

slt tout le monde
je veux savoir une strategie recursive pour regler un probléme sur ma fonction qui prend en paramétre l'adresse memoire de la racine d'un arbre AVL
et l'adresse memoire d'un noeud x de ce même arbre et qui retourne l'adresse-mémoire du noued suivant x dans l'orde "priorite au pére"
le modele d'imlantation d'un noeud typique de l'arbre AVL est le suivant :
typedef struct noeud
{
int valeur ;
struct noeud *gauche ,*droite;
}Noeud ;
typedef Noeud*Arbre;
prototype de la fonction est:
Arbre suivant(Arbre racine;Arbre x)
{}

Bonjour, on dirait que tu demandes qu'on ecrive la fonction suivant... Ce n'est pas notre rôle...

- Qu'est-ce qui te bloque ?
- Qu'est-ce que tu n'arrives pas à faire ?

Jc

PS: Cacher les pointeurs par un typedef est une mauvaise idée et habitude...

[Trap D]

De toute façon, c'est de l'algo, pas du C.
Ça veut dire quoi

retourne l'adresse-mémoire du noued suivant x dans l'orde "priorite au pére"

[Thierry Chappuis]

Salut,

Essaie de nous proposer une implémentation de ta fonction et dis-nous où sont les endroits où tu rencontre des difficultés. Au passage, c'est une bonne habitude à prendre d'écrire ton code à l'intérieur des balises prévues à cet effet. Ca sera plus lisible.

A+

Thierry

[wedoud]

merci de votre coprhention
mon probléme bien explique dans l'image suivant :

[gege2061]

Bonjour,

merci de votre coprhention
mon probléme bien explique dans l'image suivant :

Je n'ai pas trop compris le principe mais apparemment tu souhaite remonter dans l'arborescence de l'arbre ? Dans ce cas, il faut (méthode la plus simple) ajouter un champs racine dans ta structure Noeud, qui représente le noeud parent.

[Trap D]

Et peut-être un indicateur "deja_visité" pour plus de facilité de programmation.

[Trap D]

Salut,

Essaie de nous proposer une implémentation de ta fonction et dis-nous où sont les endroits où tu rencontre des difficultés.
A+

Thierry

wedoud>> c'est ça le principe du forum. On n'est pas là pour faire tes programmes, on est là pour t'aider !

[wedoud]

merci

[diogene]

Tu es tombé sur un mauvais jour des participants au forum semble t-il , car, à mon avis, ce n'est pas une question courante ni facile à traiter de façon récursive.
Puisque tu veux une version récursive, c'est la récursivité qui doit créer les liens vers les péres. Il faut donc rechercher récursivement le noeud X, mais la position de X n'est pas la bonne réponse à la question et il faut continuer un cran plus loin (et un seulement) pour obtenir le noeud suivant et sortir de la récursion
Personnellement, je pense qu'il manque un paramètre à la fonction pour indiquer si le noeud X a déjà été trouvé (et on passe alors à la recherche du suivant) ou non (et on en est encore à la première phase).

Voici une version qui, je crois, marche pour tous les noeuds du diagramme que tu as proposé. Je ne le garantis pas mais t'invite, si ça t'interresse, à le tester pour des configurations plus complexes

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
Noeud * Suivant(const Noeud * arbre, const Noeud *  X, int * found)
{
 Noeud * p = (Noeud *) arbre;
 if (arbre == X)
   {
    *found = 1;
     return arbre->gauche ? arbre->gauche :arbre->droite ;
   }
 if (*found == 0 && arbre->gauche)
   {
     p = Suivant( arbre->gauche,X,found);
     if(p == NULL)  return arbre->droite;
   }
 if(*found == 0  && arbre->droite)
     p = Suivant( arbre->droite,X,found);
 return p;
}

*found doit être initialisé à zéro

Code :

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

1
2
 int found = 0;
 NoeudSuivant =  Suivant(racine, x ,&found);

Bonne soirée