Parcours en profondeur récursif d'arbre

Version imprimable

10/12/2018, 15h50
irishupk

Parcours en profondeur récursif d'arbre

Bonjour,

Je me permet de vous solliciter, car je bloque.
Je dois écrire un parcours en profondeur par récursivité d'un arbre quelconque (N-aire).
Je sais que chaque fils peut être traité comme une liste chainée et que tant que
l'on se trouve sur la liste des fils, on applique une procédure sur tous les fils.
10/12/2018, 15h56
anapurna

salut

ici nous donnons beaucoup d'informations concernant les parcourt d'arbre

j'ai essayé d'implémenter une solution par récursivité :

Code:

1
2
3
4
5
6
7
8
9
Fonction prof_3(n=Arb):entier
debut
    si(n==NULL)
        retourner -1
    finsi
    pour i allant de 1 à f      //pour chaque fils où f est le nombre de fils
       retourner (1+max(prof_3(fg(n)),prof_3(fd(n)))         //la fonction max étant une fonction à définir qui permet de trouver la plus grande branche de chaque fils
    finpour
fin

Mais comment faire si il y a plus de 2 fils ?

11/12/2018, 10h07
anapurna

salut

tu n'as pas lu la réponse de tbc92
au lieu de FilsG et FilsD il faut parcourir tous les Fils
11/12/2018, 10h18
tbc92

Dans ton code, tu fais une boucle pour i = 1 a f... et dans cette boucle, tu n'utilises pas i.
De manière générale, une boucle sur i, où on n'utilise pas i... c'est souvent faux.

Je propose ça :

Code:

1
2
3
4
5
6
7
8
9
10
 
Fonction prof_3(n=Arb):entier
debut
	si(n==NULL)
		retourner -1
	finsi
	pour i allant de 1 à f //pour chaque fils où f est le nombre de fils
		retourner (1+max(prof_3(i(n)))//la fonction max étant une fonction à définir qui permet de trouver la plus grande branche de chaque fils
	finpour
fin

salut

raté ;)
ce serait plus un truc du genre

Code:

1
2
3
4
5
6
7
8
9
10
 
Fonction prof_3(n=Arb):entier
debut
  si(n==NULL)
     retourner -1
  finsi
  pour i allant de 1 à f //pour chaque fils où f est le nombre de fils
     retourner (1+max(fils(i),prof_3(n)))//la fonction max étant une fonction à définir qui permet de trouver la plus grande branche de chaque fils
  finpour
fin

11/12/2018, 11h45
irishupk

Merci de votre réponse, j'essaie de voir si celà correspond à mon problème
Merci
15/12/2018, 00h05
irishupk

Bonjour,

Visiblement celà ne va pas car on explore les fils mais pas les frères d'un point
15/12/2018, 11h53
tbc92

Pourquoi dis-tu qu'on ne traite pas les frères ?
Tu as implémenter cet algorithme, et ça buggue ? Et dans ce cas, montre nous ce que tu as fait.
ou bien tu regardes l'algorithme, et tu ne vois pas par quel miracle ça pourrait marcher ?

Parce que, pas de problème, on parcours bien tout l'arbre avec cet algorithme.
17/12/2018, 16h30
irishupk

En effet, après plus de réflexion, je pense que l'on parcours tout l'arbre par récurvisité.
Merci
Reste à l'implémenter maintenant