Parcours d’arbres binaires

Les arbres binaires sont des structures de données hiérarchiques (ses nœuds sont liés par des relations père-fils) et récursives.

On peut implémenter un arbre binaire et ses nœuds en Python par les classes 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 hauteur d’un arbre est égale à la plus grande des hauteurs de ses deux branches …

fonction hauteur(arbre)
    si la racine de l'arbre est une feuille
        renvoyer -1 # -1 car on ne compte pas la racine dans la hauteur d'un arbre
    sinon
        renvoyer 1 + maximum(hauteur(branche droite de la racine), hauteur(branche gauche de la racine))
    fin si
fin fonction

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

Pour calculer la taille d’un arbre, il faut là encore parcourir toutes ses branches et compter les nœuds. La fonction est également récursive.

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

Calcul du nombre de feuilles d’un arbre

Pour calculer le nombre de feuilles d’un arbre, il faut là encore parcourir toutes ses branches et compter les nœuds. La fonction est également récursive.

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

Il existe plusieurs façons de 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