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 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))

def hauteur(noeud):
    if noeud is None:
        return -1
    else:
        return 1 + max(hauteur(noeud.g), hauteur(noeud.d))

def hauteur(noeud):
    g = d = 0
    if noeud.g is not None:
        g = hauteur(noeud.g)
    if noeud.d is not None:
        d = hauteur(noeud.d)
    return 1+ max(g, d)

Calcul de la taille d’un arbre

def taille(noeud):
    if noeud is None:
        return 0
    else:
        return 1 + taille(noeud.g) + taille(noeud.d)

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___.

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

1. Parcours branche gauche
2. Visite du nœud
3. Parcours branche droite

visiterInfixe(noeud)
    si nonVide(noeud.gauche)
       visiterInfixe(noeud.gauche)
    visiter(noeud)
    si nonVide(noeud.droit)
       visiterInfixe(noeud.droit)

Ordre préfixe

1. Visite du nœud
2. Parcours branche gauche
3. 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

1. Parcours branche gauche
2. Parcours branche droite
3. 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

Exemple : l’arbre précédent doit s’afficher ainsi :

  ___5______
 /          \
10         __6
  \       /   \
   3     1     12
        / \
       9   4