Parcours postfixe d'un arbre en Scheme

Version imprimable

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:

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:

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:

((((() () . 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.

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

Code:

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:

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

23/05/2015, 17h00
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:

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:

((((((((()) . 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.
23/05/2015, 17h25
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.
23/05/2015, 18h12
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.