Le choix d’une implémentation dépend de l’utilisation que l’on en a. Typiquement, on peut utiliser la programmation orientée objet ou se contenter des types prédéfinis de Python (listes, tuples…).
I. Programmation orientée objet
1) Définition
En s’inspirant de la définition récursive d’un arbre (un arbre est composé d’un nœud et de deux sous-arbres gauche et droit), on peut définir un arbre binaire ainsi :
À noterLa notion de properties en Python (non couverte ici) pourrait permettre d’écrire plus simplement les méthodes d’accès et de modification des données de l’objet.
Abusivement, un arbre binaire vide est ici représenté par la valeur None (qui n’est donc pas de type BinTree).
2) Taille
Les différentes opérations peuvent être implémentées (de manière récursive dans les deux cas) comme des méthodes :
ou bien comme des fonctions :
3) Parcours
La fonction récursive suivante réalise un parcours préfixe et affiche les étiquettes.
Les parcours infixe et postfixe sont obtenus en permutant l’ordre des trois dernières lignes de la procédure.
II. Implémentation à partir de tuples (ou listes)
La possibilité d’imbriquer des tuples permet de représenter assez simplement des arbres binaires. Il est tout à fait possible d’utiliser des listes, même si ces dernières sont plutôt réservées à des collections d’objets de même type.
Un arbre vide est représenté par un tuple vide. Chaque nœud est un tuple de 3 valeurs contenant dans l’ordre :
- l’étiquette du nœud ;
- le sous-arbre gauche (un tuple éventuellement vide) ;
- le sous-arbre droit (un tuple éventuellement vide).
Exemple : Correspondance entre un arbre et l’implémentation à base de tuples :
('T', ('Y', 'P', ()), ('O', ('H', (), ()), ('N', (), ())))
Avec ce type de représentation, le calcul de la taille d’un arbre est aussi réalisé de manière récursive :
À noter
En Python, un conteneur vide est évalué à False. Ainsi, le test if peut s’écrire : if not arbre.