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écursive.
On peut implémenter un arbre binaire et ses nœuds en Python par les classes Arbre  et Noeud  :
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

Quelques explications ...

La fonction attend un argument de type Noeud  car chaque nœud est vu comme la racine d’un sous-arbre (une branche).

Lorsque le nœud n’existe pas (fils d’une feuille) la fonction renvoie -1 (car il faut compter à partir de zéro, profondeur du nœud racine)

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

 

Calculer l’ordre de complexité de cet algorithme.

 

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.
Implémenter en Python un algorithme permettant de déterminer la taille d’un arbre, et tester avec l’arbre défini précédemment.

 

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.

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

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)

 

Implémenter en Python ces 3 méthodes de parcours, et tester avec l’arbre défini précédemment.

 

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

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *