Parmi la famille des arbres, les arbres généraux sont caractérisés par:
-
information attachée à chaque noeud,
- non existence de l'arbre vide,
- chaque noeud a un nombre quelconque (éventuellement 0) de
sous-arbres immédiats.
Voici un exemple d'arbre général:
Lorsque le type des étiquettes attachées aux
noeuds est
a, on notera
ArbreGeneral[a] le type des
arbres généraux.
Pour les arbres binaires, les sous-arbres immédiats étaient le
sous-arbre gauche et le sous-arbre droit. Pour les arbres généraux,
comme le nombre de sous-arbres immédiats est quelconque, on ne peut
pas les caractériser aussi facilement. Aussi définit-on la notion de
forêt: une
forêt est une liste d'arbres (généraux). Nous
noterons
Foret[a] le type des forêts dont les arbres
appartiennent à
ArbreGeneral[a].
Ainsi,
Foret[a] est le type
LISTE[ArbreGeneral[a]].
Ainsi, les sous-arbres immédiats d'un arbre général constituent une
forêt: un arbre général est constitué par une racine, et l'étiquette
attachée à cette racine, et par la forêt de ses sous-arbres immédiats.
La forêt des sous-arbres immédiats d'un arbre peut être la liste vide:
l'arbre est alors réduit à une
feuille.
La barrière d'abstraction des arbres généraux ne comporte qu'un
constructeur, la fonction
ag-noeud:
;;;
;;;
;;;
;;;
Exemples
Définissons la fonction
ag-feuille spécifiée par:
;;;
;;;
Pour ce faire, il suffit de remarquer qu'il s'agit de l'arbre ayant
e comme étiquette de la racine est ayant la liste vide comme
forêt des sous-arbres immédiats:
(define (ag-feuille e)
(ag-noeud e '()))
Comme autre exemple, l'arbre dessiné ci-dessus peut être construit
avec l'expression:
(ag-noeud
'a
(list (ag-noeud
'b
(list (ag-feuille 'c)
(ag-noeud
'd
(list (ag-feuille 'j)
(ag-feuille 'e)
(ag-feuille 'f)))))
(ag-noeud
'i
(list (ag-feuille 'g)
(ag-feuille 'h)))))
Comme pour les arbres binaires, on ne vous montre rien de la représentation
des arbres ainsi construits. Aussi la barrière d'abstraction que nous
vous fournissons comporte la fonction
ab-expression, qui a
comme spécification:
;;;
;;;
Exemple
(ag-expression (ag-feuille 'a)) rend
(ag-noeud 'a (list))
Tout d'abord, revenons sur la notion de reconnaisseur. Lorsque l'on
utilise une barrière d'abstraction, les objets manipulés sont (tous)
« fabriqués » en utilisant les constructeurs et, lorsque l'on veut
définir une fonction qui a comme donnée un tel objet, on a besoin de
savoir avec quel constructeur il a été fabriqué. C'est le rôle des
reconnaisseurs, qui permettent d'aiguiller les définitions entre
« l'objet a été fabriqué par tel constructeur » ou « l'objet a été
fabriqué par tel autre constructeur » ou... Mais alors, lorsque la
barrière d'abstraction ne comporte qu'un constructeur, tout objet est
« fabriqué » en utilisant ce constructeur et on n'a pas besoin de
reconnaisseur.
Ainsi, dans la barrière d'abstraction des arbres généraux, comme il
n'y a qu'un constructeur, il n'y a pas de reconnaisseur.
;;;
;;;
;;;
;;;
;;;
Exemple
On peut écrire la définition du prédicat
ag-feuille?
spécifiée par:
;;;
;;;
en utilisant le prédicat
pair?:
(define (ag-feuille? G)
(not (pair? (ag-foret G))))
Les fonctions de la barrière d'abstraction des arbres généraux
vérifient les propriétés suivantes:
Pour toute liste d'arbres généraux (ou forêt),
F, et toute
valeur,
v:
(ag-etiquette (ag-noeud v F) ) -> v
(ag-foret (ag-noeud v F) ) -> F
Pour tout arbre général,
G:
(ag-noeud (ag-etiquette G) (ag-foret G) ) -> G
Les définitions récursives sur les arbres généraux sont plus
compliquées que les définitions sur les arbres binaires car on ne peut
pas atteindre directement tous les sous-arbres immédiats d'un arbre
donné. En fait, souvent, pour définir une fonction ayant comme donnée
un arbre général, nous aurons besoin de définir une autre fonction
ayant comme donnée une forêt, ces deux fonctions étant mutuellement
récursives (l'une appelle l'autre et inversement). On parle alors de
récursivité croisée.
Comme nous l'avons fait pour les arbres binaires, nous voudrions
calculer la profondeur des arbres généraux. La profondeur d'un arbre
peut être définie comme étant égale à un de plus que la profondeur de
la forêt constituée par ses sous-arbres immédiats, sachant que la
profondeur d'une forêt est la profondeur de son arbre le plus profond
(et elle est nulle pour la forêt vide).
Par exemple, la profondeur de l'arbre
est égale à
4
Remarquer que la profondeur d'un arbre est le nombre de niveaux lorsque
l'on dessine l'arbre comme ci-dessus.
Définissons donc la fonction
ag-profondeur ayant comme spécification
;;;
;;;
Comme cela a été dit dans l'introduction, pour définir cette fonction,
nous avons besoin de définir aussi la fonction qui rend la profondeur
d'une forêt. Cette fonction n'étant qu'une fonction auxiliaire, nous
la définissons à l'intérieur de la définition de la fonction
ag-profondeur:
(define (ag-profondeur G)
;;
;;
;;
... à faire
... à faire
... à faire
... à faire
;;
... à faire
D'après la définition de la profondeur d'un arbre, la profondeur de G
est égale à un de plus que la profondeur de la forêt de ses
sous-arbres immédiats:
(define (ag-profondeur G)
;;
;;
;;
... à faire
... à faire
... à faire
... à faire
;;
(+ 1 (profondeurForet (ag-foret G))))
Définissons maintenant la fonction qui calcule la profondeur d'une
forêt. Une forêt étant une liste, ce n'est qu'un exercice de
révisionsur les listes: la profondeur de la forêt est égale au maximum
de la profondeur du premier arbre de la forêt et de la profondeur de
la forêt obtenue, à partir de la forêt donnée, en supprimant son
premier arbre. Cette relation de récurrence n'étant définie que pour
une liste non vide, il faut extraire de l'appel récursif le cas où
(pair? F) est faux. D'où la définition:
(define (ag-profondeur G)
;;
;;
;;
(define (profondeurForet F)
(if (pair? F)
(max (ag-profondeur (car F)) (profondeurForet (cdr F)))
0))
;;
(+ 1 (profondeurForet (ag-foret G))))
Autre définition
Pour la définition de la fonction
profondeurForet, au lieu
d'écrire explicitement la récursivité comme nous l'avons fait
ci-dessus, on peut utiliser les fonctionnelles sur les listes.
Nous avons besoin de la profondeur de tous les arbres de la forêt, ce
que nous pouvons calculer en utilisant la fonctionnelle
map
-- appliquée à la fonction
ag-profondeur et à
F et qui
rend la liste des profondeurs des arbres. Ensuite, nous devons
calculer le maximum des éléments de cette liste, ce que l'on peut
faire en appliquant la fonctionnelle
reduce à cette liste, à la
fonction
max et en prenant
0 comme valeur initiale:
;;;
;;;
(define (ag-profondeur G)
;;
;;
;;
(define (profondeurForet F)
(reduce max 0 (map ag-profondeur F)))
;;
(+ 1 (profondeurForet (ag-foret G))))
Une définition encore plus concise
En fait, en utilisant les fonctionnelles
map et
reduce,
nous n'avons pas besoin de définir explicitement la fonction
profondeurForet: dans la définition de
ag-profondeur il
suffit de substituer son appel par son expression (en n'oubliant pas
les arguments de l'appel):
;;;
;;;
(define (ag-profondeur G)
(+ 1 (reduce max 0 (map ag-profondeur (ag-foret G)))))
La liste préfixe des étiquettes d'un arbre général est égale à la
concaténation de l'étiquette de sa racine et de la liste préfixe des
étiquettes de chacun de ses sous-arbres immédiats. Par exemple, la
liste préfixe de l'arbre
est égale à
(a b c d j e f i g h)
Cherchons une définition de la fonction
ag-liste-prefixe de
spécification:
;;;
;;;
Pour définir cette fonction, comme d'habitude, nous utilisons une
fonction qui « fait le travail » pour la forêt de ses sous-arbres
immédiats:
(define (ag-liste-prefixe G)
;;
;;
... à faire
... à faire
... à faire
... à faire
;;
(cons (ag-etiquette G) (liste-prefixe-foret (ag-foret G))))
La fonction
liste-prefixe-foret se définit comme d'habitude
pour les fonctions sur les listes/
(define (ag-liste-prefixe G)
;;
;;
(define (liste-prefixe-foret F)
(if (pair? F)
(append (ag-liste-prefixe (car F))
(liste-prefixe-foret (cdr F)))
'()))
;;
(cons (ag-etiquette G) (liste-prefixe-foret (ag-foret G))))
Autre définition
Encore une fois, on peut aussi utiliser les fonctionnelles habituelles
sur les listes:
;;;
;;;
(define (ag-liste-prefixe G)
;;
;;
(define (liste-prefixe-foret F)
(reduce append '() (map ag-liste-prefixe F)))
;;
(cons (ag-etiquette G) (liste-prefixe-foret (ag-foret G))))
Une définition encore plus concise
Et nous n'avons pas besoin de
définir explicitement la fonction
liste-prefixe-foret:
;;;
;;;
(define (ag-liste-prefixe G)
(cons (ag-etiquette G)
(reduce append
'()
(map ag-liste-prefixe (ag-foret G)))))
Nous voudrions afficher les arbres généraux comme nous l'avons fait
pour les arbres binaires. Autrement dit, nous voudrions définir la
fonction
ag-affichage qui, étant donné un arbre général, rend
un paragraphe
-
dont la première ligne est égale à l'étiquette de la racine de
l'arbre
- et dont les lignes suivantes sont obtenues en préfixant par un
tiret chaque ligne de la représentation ainsi définie de la suite
des sous-arbres de l'arbre.
Par exemple
ag-affichage appliquée à l'arbre
donne
"
a
-b
--c
--d
---j
---e
---f
-i
--g
--h
"
Spécification de la fonction
Ainsi, la fonction
ag-affichage a comme spécification:
;;;
;;;
;;;
;;;
;;;
Une première implantation
Idée
Comme pour les arbres binaires, la première ligne est la
représentation de l'étiquette de l'arbre et les lignes suivantes sont
obtenues en préfixant chaque ligne de la concaténation des
représentations des sous-arbres par un tiret:
Définition de la fonction
Comme pour les arbres binaires, nous définissons une fonction
auxiliaire qui rend la liste des lignes du paragraphe résultat. La
définition est alors (nous vous demandons de bien l'étudier):
(define (ag-affichage G)
;;
;;
(define (add-tiret-prefixe ligne)
(string-append "-" ligne) )
;;
;;
(define (liste-lignes-affichage G)
(cons (->string (ag-etiquette G))
(map add-tiret-prefixe
(reduce append
'()
(map liste-lignes-affichage
(ag-foret G))))) )
;;
(paragraphe (liste-lignes-affichage G)) )
Une seconde implantation
Pour écrire une définition plus efficace de cette fonction, comme nous
l'avons fait pour les arbres binaires, nous pouvons utiliser une
fonction auxiliaire,
aff-arbre, qui affiche un arbre donné en
préfixant chaque ligne par une chaîne donnée:
(define (ag-affichage G)
;;
;;
;;
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
;;
(aff-arbre "" G))
Pour un arbre et un préfixe donnés, la fonction
aff-arbre rend
le paragraphe dont la première ligne est égale à l'image de
l'étiquette de la racine de l'arbre donné précédée du préfixe donné et
dont les lignes suivantes sont égales à la représentation de la forêt
des sous-arbres de l'arbre donné préfixées par le préfixe donné et un
nouveau tiret. En utilisant la nouvelle fonction auxiliaire
aff-foret, spécifiée ci-dessous, la fonction
aff-arbre peut être définie par:
(define (ag-affichage G)
;;
;;
;;
(define (aff-arbre pref G)
(paragraphe-cons (string-append pref (->string (ag-etiquette G)))
(aff-foret (string-append pref "-") (ag-foret G))))
;;
;;
;;
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
... à faire
;;
(aff-arbre "" G))
Reste à définir la fonction
aff-foret. Donnons directement une
définition qui utilise les fonctionnelles. Que doit-on faire? Il faut
concaténer tous les éléments de la liste des paragraphes représentant
chacun des arbres de la forêt donnée, chaque ligne étant préfixée par
le préfixe donné. Pour fabriquer cette liste, nous utilisons la
fonctionnelle
map, appliquée à la fonction,
aff-arbre-pref, qui affiche un arbre
en préfixant chaque ligne par le préfixe donné; cette fonction doit
être définie à l'intérieur de la définition de
aff-foret, la
variable contenant le préfixe étant globale dans cette fonction:
(define (ag-affichage G)
;;
;;
;;
(define (aff-arbre pref G)
(paragraphe-cons (string-append pref (->string (ag-etiquette G)))
(aff-foret (string-append pref "-") (ag-foret G))))
;;
;;
;;
(define (aff-foret pref F)
;
;
;
... à faire
... à faire
;
(reduce paragraphe-append (paragraphe '()) (map aff-arbre-pref F)))
;;
(aff-arbre "" G))
Pour finir, la définition de la fonction
aff-arbre-pref n'est
qu'une application de la fonction
aff-arbre:
(define (ag-affichage G)
;;
;;
;;
(define (aff-arbre pref G)
(paragraphe-cons (string-append pref (->string (ag-etiquette G)))
(aff-foret (string-append pref "-") (ag-foret G))))
;;
;;
;;
(define (aff-foret pref F)
;
;
;
(define (aff-arbre-pref G)
(aff-arbre pref G))
;
(reduce paragraphe-append (paragraphe '()) (map aff-arbre-pref F)))
;;
(aff-arbre "" G))
Une définition plus concise
Encore une fois, nous n'avons pas besoin de
définir explicitement la fonction sur les forêts:
(define (ag-affichage G)
;;
;;
;;
(define (aff-arbre pref G)
(let ((pref2 (string-append pref "-")))
;
;
;
(define (aff-arbre-pref2 G)
(aff-arbre pref2 G))
;
(paragraphe-cons (string-append pref (->string (ag-etiquette G)))
(reduce paragraphe-append
(paragraphe '())
(map aff-arbre-pref2 (ag-foret G))))))
;;
(aff-arbre "" G))
Comme pour les arbres binaires, nous allons montrer que pour une
barrière d'abstraction il peut y avoir différentes implantations: ici
nous allons en voir trois, l'une à l'aide des Sexpressions, une autre
à l'aide des vecteurs et la troisième à l'aide des vecteurs et des
Sexpressions.
Dans cette première implantation, nous représentons les arbres
généraux à l'aide de Sexpressions: un arbre général est représenté par
une liste dont le premier élément est l'étiquette de la racine et dont
les éléments suivants constituent la forêt de ses sous-arbres
immédiats.
Définition de la fonction ag-noeud
Rappelons sa spécification:
;;;
;;;
;;;
;;;
Puisque nous avons décidé que nous représenterions un arbre par une
Sexpression dont le premier élément est l'étiquette de la racine et le
reste de la liste est la forêt de ses sous-arbres, pour construire un
arbre à partir de l'étiquette
e de la racine et de la forêt
F de ses sous-arbres, il suffit d'utiliser la fonction
cons:
(define (ag-noeud e F)
(cons e F))
Définition de la fonction ag-etiquette
Rappelons sa spécification:
;;;
;;;
Nous avons dit que l'étiquette était le premier élément de la liste
qui représente l'arbre:
(define (ag-etiquette g)
(car g))
Définition de la fonction ag-foret
Rappelons sa spécification:
;;;
;;;
;;;
Nous avons dit que la forêt des sous-arbres était constituée par la
liste qui représente l'arbre hormis son premier élément:
(define (ag-foret g)
(cdr g))
Implantons maintenant les arbres généraux en utilisant des vecteurs:
un arbre général est représenté par un vecteur, le premier composant
du vecteur contenant l'étiquette de la racine de l'arbre et les
composants suivants contenant les représentations des sous-arbres
immédiats de l'arbre.
Définition de la fonction ag-noeud
Rappelons sa spécification:
;;;
;;;
;;;
;;;
Nous devons rendre un vecteur dont nous connaissons le premier composant et
la liste des autres composants. Pour ce faire, on peut utiliser la fonction
list->vector:
(define (ag-noeud e F)
(list->vector (cons e F)))
Définition de la fonction ag-etiquette
Rappelons sa spécification:
;;;
;;;
L'étiquette étant le premier composant (celui d'indice 0) du vecteur
qui représente l'arbre, il suffit d'appliquer la fonction
vector-ref:
(define (ag-etiquette g)
(vector-ref g 0))
Définition de la fonction ag-foret
Rappelons sa spécification:
;;;
;;;
;;;
La forêt des sous-arbres étant la liste des arbres contenu dans les
composants (hormis le premier) du vecteur, nous utilisons la fonction
vector->list:
(define (ag-foret g)
(cdr (vector->list g)))
Dans cette implantation, nous représentons un arbre général par un
vecteur, de longueur deux, dont le premier composant est l'étiquette
de la racine et dont le second composant est la liste de ses
sous-arbres immédiats (c'est donc la forêt de ses sous-arbres
immédiats).
Définition de la fonction ag-noeud
Rappelons sa spécification:
;;;
;;;
;;;
;;;
D'après la spécification de l'implantation des arbres donnée
ci-dessus, cette fonction doit rendre un vecteur dont le premier
composant est l'étiquette donnée et dont le second composant est la
forêt donnée:
(define (ag-noeud e F)
(vector e F))
Définition de la fonction ag-etiquette
Rappelons sa spécification:
;;;
;;;
Il suffit de rendre le premier composant du vecteur (celui d'indice 0):
(define (ag-etiquette g)
(vector-ref g 0))
Définition de la fonction ag-foret
Rappelons sa spécification:
;;;
;;;
;;;
Il suffit de rendre le second composant du vecteur (celui d'indice 1):
(define (ag-foret g)
(vector-ref g 1))
