Parcours d’arbres binaires
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 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.
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