Discussion :

[ArtyBours]

Bonjour à vous,

Pour un arbre binaire A, j'ai réussis à écrire une fonction qui calcule la somme de la valeur de ses étiquettes ((ab-somme A)) et une seconde qui calcule le nombre de feuilles pour A ((ab-nb-feuilles A)).
Maintenant si je souhaitais faire tout ça dans une seule et même fonction, je pourrais faire ainsi par exemple:

;;; ab-nb-et-somme-BAD: ArbreBinaire[Nombre] -> Couple[Nat Nombre]
(define (ab-nb-somme-BAD A)
(list (ab-nb-feuilles A) (ab-somme A)))

Le seul problème étant que mon programme va parcourir 2 fois A.

Comment faire pour créer une fonction qui pourrait faire cela en ne parcourant qu'une seule fois l'arbre ?

Cordialement

[stendhal666]

NB: je te le mets en Common LISP pcq ma syntaxe scheme est un peu rouillée mais tu devrais t'y retrouver:

Tu ne donnes pas trop de précision sur la façon dont tu représentes l'arbre binaire. J'imagine que chaque noeud est soit nul, soit un atome, soit une liste de 3 noeuds, par ex:

'(1 2 3)
<=>
1
/\
23

'(1 2)
<=>
1
/\
2 Nil

Donc pour chacune de tes fonctions tu aurais, par ex:

Code LISP :

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

1
2
3
4
5
6
7
8
9
10
11
(defun somme-labels (node)
  (cond 
    ((null node) 0)
    ((atom node) node)
    (T (+ (car node) (somme-labels (cadr node)) (somme-labels (caddr node))))))
 
(defun count-leaves (node)
  (cond
    ((null node) 0)
    ((atom node) 1)
    (T (+ (count-leaves (cadr node)) (count-leaves (caddr node))))))

On peut donc capitaliser sur la ressemblance de structure entre les deux et renvoyer un résultat sous forme de tuple.

Je définis en premier lieu une fonction pour additionner 2 tuples:

Code LISP :

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

1
2
3
4
(defun add-cons (a b &rest r)
  (let ((s (cons (+ (car a) (car b)) (+ (cdr a) (cdr b)))))
    (if (null r) s
        (add-cons s (car r) (cdr r)))))

Et je l'utilise dans la fonction composée:

Code LISP :

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

1
2
3
4
5
(defun somme-labels-nombre-feuilles (node)
  (cond
    ((null node) (cons 0 0)
    ((atom node) (cons node 1)
    (T (add-cons (cons node 0) (somme-labels-nombre-feuilles (cadr node)) (somme-labels-nombre-feuilles (caddr node))))))

Bien évidemment il faut adapter pour ton dialecte et la façon dont tu représentes l'arbre

[byjav]

Je pense qu'une fonction d'ordre supérieur du type de fold serait utile. Cette fonction parcourirait l'arbre en applicant une fonction donnée à ces nœud et en accumulant les resultats. Je suppose que cet algorithme est partiellement réalisé dans les fonctions ab-somme et ab-nb-feuilles. Alors on pourrait (ré)écrire les fonctions en question comme ça :

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
(define (ab-somme a)
  (tree-fold a (lambda (noeud acc 0)
                 (+ acc (etiquette noeud)))))

(define (ab-nb-feuilles a)
  (tree-fold a (lambda (noeud acc 0)
                 (if (leaf? noeud)
                     acc
                     (+ acc 1)))))

(define (ab-nb-somme a)
  (tree-fold a (lambda (noeud acc '(0 0))
                 (let ((etiquettes (car acc))
                       (feuilles (cadr acc)))
                   (list (+ (etiquette noeud) etiquettes)
                         (if (leaf? noeud)
                             feuilles
                             (+ feuilles 1)))))))

L'ayant écrit, je commence à douter que le code devient plus court avec la fonction d'ordre supérieur. :-/ Mais il semble assez compréhensible.

[jack-ft]

Le seul problème étant que mon programme va parcourir 2 fois A.

Comment faire pour créer une fonction qui pourrait faire cela en ne parcourant qu'une seule fois l'arbre ?

Je ne suis pas un pro des profilers, mais je ne crois pas que le double parcours soit si pénalisant (sauf si allait chercher les éléments de l'arbre dans une base à objets, par exemple).

Pour que ta fonction retourne 2 résultats en parcourant une seule fois l'arbre, il faut:
- soit utiliser des variables pour accumuler les résultats (avec probablement une perte de lisibilité et de généricité)
- soit accumuler les résultats au fur et à mesure (chaque appel récursif retournerait un cons), avec également une perte de lisibilité et de généricité, et probablement d'efficacité.

Bref, je trouve que la solution triviale, avec 2 fonctions dont on combine les résultats, me paraît tout à fait satisfaisante (à la fois en termes de structuration/lisibilité et d'efficacité)!

(d'ailleurs, j'aimerais bien savoir dans quelles circonstances on pourrait avoir besoin d'une telle fonction, plutôt que juste des 2 fonctions proposées?!?!)