Discussion :

[Flo963]

Bonjour,

Je suis actuellement un cours sur la récursivité en Scheme, et je galère un peu sur les arbres. Je suis sur une fonction qui rend une liste des valeurs en ordre postfixe (les feuilles avant la racine).

Voilà ma fonction :

Code :

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

1
2
3
4
5
6
(define (liste-postfixe B)
  (if (ab-noeud? B)
       (cons (liste-postfixe (ab-gauche B))
             (cons (liste-postfixe (ab-droit B))
       (ab-etiquette B)))
      '()))

que j'applique à cet arbre :

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
(liste-postfixe (ab-noeud 1
                  (ab-noeud 2
                     (ab-noeud 4
                               (ab-noeud 9 (ab-vide) (ab-vide) )
                               (ab-noeud 3 (ab-vide) (ab-vide)))
                     (ab-noeud 5
                               (ab-noeud 3 (ab-vide) (ab-vide) )
                               (ab-noeud 0 (ab-vide) (ab-vide))))
                  (ab-noeud 3
                     (ab-noeud 6
                               (ab-noeud 2 (ab-vide) (ab-vide) )
                               (ab-noeud 3 (ab-vide) (ab-vide)))
                     (ab-noeud 7
                               (ab-noeud 6 (ab-vide) (ab-vide) )
                               (ab-noeud 8 (ab-vide) (ab-vide ) )))))

et voilà le résultat :

Code :

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

((((() () . 9) (() () . 3) . 4) ((() () . 3) (() () . 0) . 5) . 2) (((() () . 2) (() () . 3) . 6) ((() () . 6) (() () . 8) . 7) . 3) . 1)

Il s'agit bien des valeurs en ordre postfixe mais comme vous le voyez, il y a pas mal de bordel en plus, ce qui est lié certainement à un "cons" en trop ou mal placé, mais pour l'instant je ne vois pas comment faire autrement.

Quelqu'un connaissant le scheme a-t-il une idée ?

Mercie d'avance.

[yahiko]

Après une phase de dérouillage de Scheme (ça fait une éternité) voilà l'algo simple.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (postfixe arbre)
  (if (not (null? arbre))
      (if (not (null? (cdr arbre)))
          (cons (cons (postfixe (car (cdr arbre)))
                      (postfixe (cdr (cdr arbre)))
                      )
                (list (car arbre))
          )
          (list (car arbre))
      )
      ()
  )
)

La fonction postfixe appliquée à l'arbre binaire (1 (2 (4) (5)) (3)) donne le résultat suivant

Code :

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

(((((4) (5)) 2) (3)) 1)

[Flo963]

On ne doit pas utiliser la même version de Scheme.
Je ne peux pas écrire (car arbre) dans ma version. Il me répond que "car" réclame une liste.
En essayant de suivre ton algorithme, je peux écrire :

Code :

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

1
2
3
4
5
6
7
 
(define (liste-postfixe B)
  (if (ab-noeud? B)
       (cons (cons (liste-postfixe (ab-gauche B))
             (liste-postfixe (ab-droit B)))
       (ab-etiquette B))
      '()))

Ce qui me donne :

Code :

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

((((((((()) . 9) (()) . 3) . 4) (((()) . 3) (()) . 0) . 5) . 2) (((((()) . 2) (()) . 3) . 6) (((()) . 6) (()) . 8) . 7) . 3) . 1)

C'est-à-dire la même chose. Je n'ai pas une idée très précise de ce que fait la fonction, et ça rend le bug difficile à corriger.

[yahiko]

Le code que j'ai posté fonctionne avec toutes les versions de Scheme, alors que celui que tu utilises fait appel à des définitions qui sont propres à ton devoir (car je suppose qu'il s'agit d'un devoir scolaire).

Tu sembles avoir des difficultés tout autant avec la syntaxe de Scheme qu'avec l'algorithme pourtant simple du parcours postfixe.

Si tu as des questions spécifiques au langage Scheme, je t'invite à poster ici : http://www.developpez.net/forums/f51...onnels/scheme/

Une fois que tu auras compris les bases de Scheme, tu pourras revenir ici pour parler de l'algorithme proprement dit.

[Flo963]

Je pense connaître maintenant la syntaxe du Scheme, mais j'ai travaillé sur des listes jusque-là et non sur des arbres. C'est cette structure de données que je connais mal.
Merci pour ton aide en tout cas.