TD Programmation fonctionnelle CS-110

Chapitre 3 : Arbres

Notations

Constructeurs, testeur et sélecteurs

- Élément : un type

ArbreBin : le type arbre binaire d'Éléments.

- $/\backslash$ dénote l'arbre binaire vide. Le testeur associé est EstVide?

EstVide? : un ArbreBin $\rightarrow$ un booléen

- $/G,r,D\backslash$ dénote l'arbre binaire non vide de racine $r$, de sous-arbre gauche $G$ et de sous-arbre droit $D$.
Les sélecteurs associés sont Gauche, Droit et Racine.

Gauche : un ArbreBin non vide $\rightarrow$ un ArbreBin {Gauche( $/G,r,D\backslash$)$= G$}

Droit : un ArbreBin non vide $\rightarrow$ un ArbreBin {Droit( $/G,r,D\backslash$)$= D$}

Racine : un ArbreBin non vide $\rightarrow$ un Élément {Racine( $/G,r,D\backslash$)$= r$}

Notations abrégées pour décrire les arbres non vides

- $//r\backslash\backslash$ est une forme abrégée de $/ /\backslash ,r,/\backslash \backslash$, et dénote un arbre binaire singleton de racine r. Le testeur associé est EstSingleton?.

- $//G,r\backslash\backslash$ est une forme abrégée de $/G ,r,/\backslash \backslash$ où $G$ est non vide : la racine de cet arbre est un noeud unaire gauche. Le testeur associé est EstUnaireG?.

- $//r,D\backslash\backslash$ est une forme abrégée de $/ /\backslash ,r,D\backslash$ où $D$ est non vide : la racine de cet arbre est un noeud unaire droit. Le testeur associé est EstUnaireD?.

- $//G,r,D\backslash\backslash$ est une forme abrégée de $/G,r,D\backslash$ où $G$ et $D$ sont non vides : la racine de cet arbre est un noeud binaire. Le testeur associé est EstBinaire?.

Modèles d'analyse récurrente

	Forme des équations	Forme des réalisations récursives de f(X)
	de récurrence de f
Modèle 1:	f($/\backslash$) =	Si EstVide?(X) alors ...
avec	f( $/G,r,D\backslash$) =	sinon soit r=Racine(X), G=Gauche(X), D=Droit(X)
l'arbre vide		dans ...
		soit r=Racine(X), G=Gauche(X), D=Droit(X)
	f( $//r\backslash\backslash$) =	dans selon
Modèle 2:	f( $//G,r\backslash\backslash$) =	EstSingleton?(X):...
sans	f( $//r,D\backslash\backslash$) =	EstUnaireG?(X):...
l'arbre vide	f( $//G,r,D\backslash\backslash$) =	EstUnaireD?(X):...
		EstBinaire?(X):...

Anne Benoit - Octobre 2001