Algorithme de recursion (un peu rouillée)

Bonjour,

Désolée, mais cela fait un peu de temps que je n'ai pas utilisé d'algorithme de récursion et là, je m'embrouille un peu...

Je voudrais si possible meme passer par un algorithme itératif, mais voici donc mon problème :

Je voudrais pouvoir parcourir un arbre binaire de la manière suivante :
1 - Chercher une feuille du coté du fils droit.
2 - Si la feuille est valide (c'est moi qui décide de cela avec une autre fonction), c'est super ! Fin de l'algorithme.
Sinon, chercher alors de la meme maniere mais en repartant du fils gauche d'origine !!!

Je veux dire que si j'ai un noeud N1, je vais d'abord regarder tous ces fils droits, et si je n'en trouve pas un qui me conviennent, je veux repartir depuis N1 vers le fils gauche, qui se charge à son tour de regarder tout les fils droits, etc...

Foulala, je suis sure que je vais finir par le trouver toute seule à force de reposer le problème... Mais c'est pas évidente à chaque fois...

Citation:

Envoyé par zuzuu

Je voudrais si possible meme passer par un algorithme itératif

Effectivment, c'est plus simple de le faire en itératif. ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
If NOT TrouveFilsDroit(Root.FilsDroit) then
  TrouveFilsDroit(Root.FilsGauche)
End If
 
Function TrouveFilsDroit(Node Depart)
  Node cursor = Depart
 
  Do While cursor.isvalid
    If moncritere(cursor)=True Then
      Rem trouvé
      Exit Function = True
    End If
    cursor = cursor.FilsDroit
  Loop
 
  Rem pas trouvé
  Exit Function = False
 
End Function

Citation:
Envoyé par pseudocode
Effectivment, c'est plus simple de le faire en itératif. ;)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 If NOT TrouveFilsDroit(Root.FilsDroit) then TrouveFilsDroit(Root.FilsGauche) End If Function TrouveFilsDroit(Node Depart) Node cursor = Depart Do While cursor.isvalid If moncritere(cursor)=True Then Rem trouvé Exit Function = True End If cursor = cursor.FilsDroit Loop Rem pas trouvé Exit Function = False End Function
Euh... Si je comprends bien ton code, tu explore la diagonale droite de ton arbre (c'est à dire uniquement les noeuds droit), et si ça échoue, tu remontes, et tu explores uniquement la diagonale droite du sous arbre gauche ! Moralité, au final, tu n'explores que deux feuilles ! je ne suis pas convaincu que ce soit ce qui est demandé !

Ne connaissant pas VB, code OCaml :
Code:

1 2 3 4 5 6 7 let rec trouver_fils = | Noeud (fg, fd) -> (match trouver_fils fd with | None -> trouver_fils fg | Some val -> Some res) | Feuille val -> if valid val then Some val else None
On teste ainsi les feuille de droite à gauche.

Finalement j'ai inversé ma droite et ma gauche...
Voici ce que je voudrais vraiment faire, c'est finalement un chouilla un peu plus compliqué :

Imaginer que vous ayez des rectangles (hi, et oui toujours ces fameux rectangles) qui soit classés de la manière suivante (en gros du plus gros au plus petit), sachant que si un rectangle à une hauteur plus grosse que les autres, il passe avant).

Ensuite, j'ai un premier rectangle comme ceci dans ma fenetre :
Code:

1 2 3 4 5 6 7 8 9 10 11 ____________________________ ///////// | ///////// | ///////// | | | | | | ____________________________|
Je voudrais rajouter un autre rectangle soit en bas de celui ci, soit à droite.
En fait, j'ai un arbre binaire pour stocker tout mes rectangles. Si on part du premier, le second rectangle sera ajouté soit à droite (donc la feuille droite), soit en dessous (soit la feuille gauche).

Donc, jusque là, c'est assez simple.
Maintenant je voudrais ajouter mon rectangle du coté qui me fera perdre le moins de place...

Comme mes rectangles sont classés par taille (sachant que ceux qui sont le plus haut seront en premier), je voudrais ajouter à gauche (en bas), si le je perd moins de place que si je l'ajoute à droite selon l'exemple suivant :

*** <- le nouveau rectangle à ajouter...
Code:

1 2 3 4 5 6 7 8 9 10 11 ____________________________ ///////// *** | ///////// | ///////// | | | | | | ____________________________|
# -> espace perdu
Code:

1 2 3 4 5 6 7 8 9 10 11 ____________________________ ///////// ***############# | ///////// ################ | ///////// ################ | | | | | | ____________________________|
Alors que si je l'ajoute en bas, cela donnera...
Code:

1 2 3 4 5 6 7 8 9 10 11 ____________________________ ///////// | ///////// | ///////// | ***################### | ###################### | ###################### | ###################### | ###################### | ######################______|
Donc , dans cette exemple, il faudrait mieux que j'ajoute à droite mon rectangle...

Ensuite, cela devrait donner ceci quand il y aura plus de rectangle :

//////
//////
***##############

Voici l'espace perdu si on ajoute à droite du dernier.

//////
//////
***
###
###

Voici l'espace perdu si on ajoute à gauche du dernier...

Et ainsi de suite ..

Si j'ai bien compris, tu veux faire un parcours en profondeur d'abord de ton arbre.

Tu as tout ce dont tu as besoin ici : http://rperrot.developpez.com/articl.../arbres/#LVI-A

Il est possible de transformer ce type d'algo en itératif, mais ça t'oblige à gérer une structure de pile, qui contiendra le chemin en cours de traitement, par exemple sous la forme : ggddg (d= droit, g = gauche). Pour remonter, tu dépiles, quand tu décide d'aller à gauche, tu empiles g, idem à droite.

Merci !! Revoir les bases ça fait du bien !

Je vais m'en sortir je pense ;)