Arbre binaire appel recursive

Version imprimable

03/08/2006, 14h59
wedoud

Arbre binaire appel recursive

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)
{}
03/08/2006, 15h07
fearyourself

Citation:

Envoyé par 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)
{}

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...
03/08/2006, 15h21
Trap D

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

Citation:

retourne l'adresse-mémoire du noued suivant x dans l'orde "priorite au pére"
03/08/2006, 15h22
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
03/08/2006, 15h56
wedoud

1 pièce(s) jointe(s)

merci de votre coprhention
mon probléme bien explique dans l'image suivant :
03/08/2006, 16h18
gege2061

Bonjour,

Citation:

Envoyé par wedoud

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.
03/08/2006, 16h34
Trap D

Et peut-être un indicateur "deja_visité" pour plus de facilité de programmation.
03/08/2006, 18h42
wedoud

votre réponse SVP.
03/08/2006, 18h46
Trap D

Citation:

Envoyé par wedoud

votre réponse SVP.

Aide-toi et le ciel t'aidera :evilred:
03/08/2006, 19h14
_kal_

Citation:

Envoyé par wedoud

votre réponse SVP.

Tu t'es cru sur la hotline wanadoo ou quoi ? 8O

Déjà, corrige tes fautes d'orthographe, et peut-être plus de monde essaira de te comprendre...
03/08/2006, 19h26
wedoud

désolé les EXPERTS:roll:
03/08/2006, 19h40
Trap D

Citation:

Envoyé par mujigka

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 !
03/08/2006, 19h44
wedoud

merci

Tu es tombé sur un mauvais jour des participants au forum semble t-il :lol: , 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:

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:

1 2 int found = 0; NoeudSuivant = Suivant(racine, x ,&found);
Bonne soirée

03/08/2006, 20h31
wedoud

merci diogene de votre Compréhension
merci merci
jezaka lahou khayrane
merci pour tous