Parcours d’arbres binaires
Arbre
et Noeud
comme celles-ci :class Arbre: def __init__(self, racine = None): self.racine = racine # type : Noeud class Noeud: def __init__(self, v, g = None, d = None): self.g = g # type Noeud self.d = d # type Noeud self.v = v
Calcul de la hauteur d’un arbre
Pour calculer la hauteur d’un arbre, il faut parcourir toutes ses branches et retenir la profondeur de la feuille la plus éloignée.
La fonction est bien entendue récursive : la taille d’un arbre est égale à la somme des tailles de ses deux branches …
fonction hauteur(noeud) if noeud est un nœud vide renvoyer -1 # -1 car on ne compte pas la racine dans la hauteur d'un arbre sinon renvoyer 1 + maximum(hauteur(noeud.droit), hauteur(noeud.gauche)) fin si fin fonction
Implémenter cet algorithme en Python, et tester avec l’arbre défini par :
ng, nd = Noeud(9), Noeud(4) ng, nd = Noeud(1, ng, nd), Noeud(12) nd = Noeud(6, ng, nd) ngd = Noeud(3) ng = Noeud(10, d = ngd) arbre = Arbre(Noeud(5, ng, nd))

Calcul de la taille d’un arbre
Calcul du nombre de feuilles d’un arbre
Implémenter en Python un algorithme permettant de compter le nombre de feuilles d’un arbre, et tester avec l’arbre défini précédemment.
Test de l’égalité de deux arbres
Pour tester si un arbre est égal à un autre, on souhaite utiliser la méthode spéciale ___eq___
.
__eq__
pour la classe Arbre
, et une autre pour la classe Noeud
(récursive celle-ci).
Parcourir un arbre
Ordres infixe, préfixe ou suffixe
Ces trois modes se distinguent uniquement par l’ordre avec lequel on réalise les parcours des branches droite et gauche par rapport à la visite d’un nœud :
Ordre infixe
- Parcours branche gauche
- Visite du nœud
- Parcours branche droite
visiterInfixe(noeud) si nonVide(noeud.gauche) visiterInfixe(noeud.gauche) visiter(noeud) si nonVide(noeud.droit) visiterInfixe(noeud.droit)
Ordre préfixe
- Visite du nœud
- Parcours branche gauche
- Parcours branche droite
visiterPréfixe(noeud) visiter(noeud) si nonVide(noeud.gauche) visiterPréfixe(noeud.gauche) si nonVide(noeud.droit) visiterPréfixe(noeud.droit)
Ordre suffixe
- Parcours branche gauche
- Parcours branche droite
- Visite du nœud
visiterSuffixe(noeud) si nonVide(noeud.gauche) visiterSuffixe(noeud.gauche) si nonVide(noeud.droit) visiterSuffixe(noeud.droit) visiter(noeud)
Parcours en largeur d’abord
Le principe de ce parcours est de visiter le nœud le plus proche de la racine qui n’a pas déjà été visité, ainsi on va d’abord visiter la racine, puis les nœuds à la profondeur 1, puis 2, etc… D’où le nom parcours en largeur.
L’implémentation va nécessiter l’utilisation une structure en file : on met « en attente » les pères, puis on visite.
f = File f.enfiler(noeud) //on place la racine dans la file tant que f non vide : n = f.defiler() visiter(n) si n.gauche n'est pas vide f.enfiler(n.gauche) fin si si n.droit n'est pas vide f.enfiler(n.droit) fin si fin tant que
Affichage
Arbre
d’une méthode __repr__
permettant l’affichage d’un arbre sous forme de chaînes de caractères.Exemple : l’arbre précédent doit s’afficher ainsi :
___5______ / \ 10 __6 \ / \ 3 1 12 / \ 9 4