Discussion :

[Bakura]

Bonsoir à tous !

J'ai un petit exercice d'algorithmique en cours qui me pose quelques soucis. L'objectif est de créer un parcours "binaire" à partir d'un arbre. Par exemple, imaginons l'arbre binaire suivant (on considère que l'arbre est forcément binaire) :

Code :

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

1
2
3
4
5
6
7
                      D (100)
          B (10) -  
                      E (101)
A (1) - 
                      F (110)
          C (11)  -
                      G (111)

EDIT : mince, les espaces n'ont pas été pris en compte. Donc A est le noeud racine, B et C le fils gauche et droite respectivement, D et E les fils gauche et droite du noeud B respectivement, et F et G les fils gauche et droite du noeud C, respectivement.

L'algorithme (qui doit être en fait codé en C...) prend deux pointeurs vers des noeuds N1 et N2 (on assume pour simplifier que N2 est bien un sous-arbre de N1). En fait, en partant du noeud N1 dont la valeur binaire vaut 1, le noeud enfant de gauche effectue un décalage binaire vers la droite et le noeud enfant de droite un décalage binaire vers la droite + 1.

Si par exemple N1 est A, et N2 est D, le programme doit donc renvoyer le nombre binaire 100, et si N2 est F, il doit renvoyer 110.

L'algorithme doit être récursif.

J'ai essayé énormément de choses avec plusieurs types d'opérateurs binaires. Au début je m'étais orienté en parcourant l'arbre, et lorsqu'on arrive effectivement au noeud souhaité on renvoie 1, cette valeur étant soit décalée soit décalée + 1 s'il s'agit du noeud gauche ou droit, puis effectuer un OU binaire sur les valeurs des noeuds droite et gauche, mais cela ne fonctionne évidemment pas puisque je ne descends pas, mais je remonte...

J'en suis arrivé à des solutions comme celles-ci :

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
unsigned int GetPath (const Tree * s, const Tree * st)
{
	unsigned int pathLeft = 1;
	unsigned int pathRight = 1;
 
	if ((s == NULL) || (st == NULL))
		return 0;
 
	if (s == st)
		return 1;
 
	//pathLeft = (pathLeft << 1) * GetPath (s->sag, st);
	//pathRight = ((pathRight << 1) | 1) * GetPath (s->sad, st);
        pathLeft = GetPath (s->sag, st) << 1;
	pathRight = GetPath (s->sad, st) << 1 | 1;
 
	return (pathLeft | pathRight);
}

Mais qui ne fonctionnent que si on suit un chemin toujours dans la même direction (droite droite droite... ou gauche gauche gauche...).

J'avoue que je sèche un peu là (ayant BEAUCOUP de mal avec le récursif également...), j'ai essayé plein de solutions en utilisant des XOR, des OR... Mais je pense que la solution n'est pas là.

[Obsidian]

Bonsoir,

Ça marche mieux avec la balise CODE :-)

Code txt :

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

1
2
3
4
5
6
7
                      D (100)
          B (10) -  
                      E (101)
A (1) - 
                      F (110)
          C (11)  -
                      G (111)

Ton énoncé est un peu confus, mais je crois comprendre que l'on te donne deux nœuds, le second étant un descendant du premier, et que tu veux obtenir le chemin qui relie l'aïeul à son enfant. Ceci sous-entend effectivement que le second nœud fait forcément partie du sous-arbre descendant du premier. Admettons.

N1 a beau désigner un sous-arbre, il reste la racine de celui-ci. Il est donc toujours numéroté « 1 ». Cela implique également que le numéro d'un nœud est forcément non-nul. Tu peux donc utiliser le zéro pour indiquer que le nœud recherché n'a pas été trouvé (ce qui sera forcément le cas pour au moins une de tes branches, s'il n'y a pas de doublon).

L'astuce réside dans le fait qu'il faut passer le numéro du nœud courant à la fonction récursive qui, elle, se charge d'en déduire ceux de ses enfants. Ta fonction a donc besoin de trois paramètres : le nœud à chercher, le nœud en cours, et le numéro du nœud en cours.

Par conséquent :

• Tu appelles ta fonction récursive depuis main() en passant le nœud à chercher, le sommet de l'arbre ou du sous-arbre et − a priori − la valeur « 1 » comme identifiant du nœud initial ;
• Tu renvoies zéro si les deux fils sont NULL (dans ton exemple, tu utilises || au lieu de &&). Sinon, c'est qu'il y a encore une branche à explorer et, donc, de l'espoir ; :-)
• Tu renvoies n si le nœud à rechercher est le même que le nœud courant. Ça signifie qu'on l'a atteint ;
• Sinon, tu renvoies effectivement le OU « | » des résultats des deux appels récursifs à ta fonction : « GetPath () | GetPath ». L'un des deux étant forcément nul, le résultat restera cohérent. Tu passes à l'une et l'autre les valeurs respectives des fils gauche et droit, et les identifiants 2n et 2n+1.

Le problème devrait être résolu. Le programme te renverra « 0 » si le nœud à rechercher n'existe pas.

[Bakura]

Salut,

Tout d'abord merci de ta réponse et désolé de ne pas avoir répondu plus tôt. Effectivement cette méthode est très simple et fonctionne, je crois que c'est celle que je vais rendre de toute façon.

Le truc c'est, qu'en cours, le prof a donné comme prototype de la fonction GetPath ceci :

Code :

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

unsigned int GetPath (const Tree * s, const Tree * st)

.

D'où le fait que j'ai essayé de trouver une solution en me passant d'un troisième paramètre dans la fonction. Après je ne sais pas si c'est une erreur de sa part, j'imagine effectivement qu'il y a un moyen de résoudre ce problème sans passer par un troisième paramètre, mais ça complique effectivement l'algo...