---
# System prepended metadata

title: Exercice sur le calcul recursif de la taille d'un arbre en Python

---

# Calcul recursif de la taille d'un arbre en Python


On considere l'arbre represente a la page 276 du manuel de Terminale. On utilise les classes *Arbre* et *Noeud* telles que definies en syntaxe UML a la page 277.

## Implementation en Python des-dites classes

Les classes *Arbre* et *Noeud* peuvent etre implementes de la maniere suivante en langage Python.
```python=

class Noeud:
	def __init__(self, clef):
		self.Clef = clef


class Arbre:
	def __init__(self, clef):
		self.Racine = Noeud(clef)
		self.Sag = None
		self.Sad = None

```

**Note :** On utilise la mot cle *'None'* pour indiquer l'absence de sous-arbre gauche (SAG) et/ou de sous-arbre droit (SAD).

**Note :** Ici, un arbre est entierement defini par la donnee de trois elements : *(Racine, Sag, Sad)*

**Note :** Par defaut, au moment de sa construction cet arbre ne contient rien de plus que sa racine (cad un seul noeud), les valeurs de *Sag* et *Sad* sont initialises a *None*

## Construction de l'arbre d'exemple

On utilise les code de la page 277 qui permet de construire l'arbre represente a la page 276. Il s'agit d'un arbre binaire de taille 9 et de profondeur 3. On reutilise la classe *Arbre* definie plus haut.

```python=   
a = Arbre('A')
a.Sag = Arbre('B')
a.Sag.Sag = Arbre('C')
a.Sag.Sag.Sag = Arbre('D')
a.Sag.Sag.Sad = Arbre('E')
a.Sad = Arbre('F')
a.Sad.Sag = Arbre('G')
a.Sad.Sad = Arbre('H')
a.Sad.Sad.Sad = Arbre('I')
```

**Rappel :**  Par nature, un sous-arbre (SAG ou SAD) est aussi un arbre. 

## Fonction recursive pour calculer la taille:

On propose une implementation en Python de la fonction T(B) definie a la page 47 du manuel. En observant cette formule on voit que cette fonction doit prendre en paramettre un objet dont a nature est un arbre et qu'elle doit renvoyer un entier naturel correspondant a la taille de l'arbre en question.

**Remarque :** Cette observation permet de derteminer le *prototype* de la fonction (cad la nature des arguments qu'elle prend en entree et le type de la valeur de retour). Ceci est une aide utile lorsque on ne sait pas par ou commencer.

``` python= 
def taille(arbre: Arbre) -> int:
    if arbre is None:   # Il s'agit ici du cas d'arret de la fonction recursive
        return 0
    else:
        return taille(arbre.Sag) + taille(arbre.Sad) + 1   # La fonction taille() s'appelle elle-meme
    
print(taille(a))
# OUT: 9
```

**Remarque :** On voit ici que la fonction *taille* est recursive car elle s'appelle elle-meme dans sa propre definition (ligne 5).

## Conclusion

Vous avez là un exemple d'algorithme recursif appliqué à une structure d'arbre.