Type abstrait Arbre binaire

Nous avons vu ce qu'était un arbre binaire, ainsi que le vocabulaire général et les différentes mesures sur les arbres.

Avant de passer à la partie implémentation, proposons une interface minimale du type abstrait Arbre.

Note

Dans toute la suite du cours, on utilisera le type Arbre pour désigner un arbre binaire.

On rappelle qu'un arbre binaire est soit :

• un arbre vide
• un arbre caractérisé par un noeud racine, un sous-arbre gauche et un sous-arbre droit, eux-mêmes étant des arbres binaires.

Type abstrait Arbre

Utilise : Noeud, Element, Bool
Opérations :
     \(nvABV :~\rightarrow Arbre\)
     \(nvAB :~Noeud \times Arbre \times Arbre \rightarrow Arbre\)
     \(racine :~Arbre \rightarrow Noeud\)
     \(gauche :~Arbre \rightarrow Arbre\)
     \(droite :~Arbre \rightarrow Arbre\)
     \(contenu :~Noeud \rightarrow Element\)
     \(est\_vide :~Arbre \rightarrow Bool\)
Préconditions (\(a\) : Arbre) :
     \(racine(a)\) est défini si et seulement si \(\neg est\_vide(a)\)
     \(gauche(a)\) est défini si et seulement si \(\neg est\_vide(a)\)
     \(droite(a)\) est défini si et seulement si \(\neg est\_vide(a)\)