Algorithmes sur les arbres binaires (Partie 1)

Nous parlerons ici uniquempent des arbres binaires. Voici l'arbre que nous utiliserons comme exemple pour commencer.

Taille d'un arbre

1) Quelle est la taille de cet arbre ?

2) Proposez un algorithme récursif permettant de calculer la taille d'un arbre.

taille(arbre):
    taille = 1
    si arbre.gauche est non vide:
        taille = taille + taille(arbre.gauche)
    si arbre.droit est non vide:
        taille = taille + taille(arbre.droit)
    retourner taille

taille(arbre):
    Si l'arbre est vide:
        retourner 0
    Sinon:
        retourner 1 + taille(sous-arbre gauche) + taille(sous-arbre droit))

Hauteur d'un arbre

3) Quelle est la hauteur de cet arbre ?

4) Proposez un algorithme récursif permettant de calculer la hauteur d'un arbre.

hauteur(arbre):
    si arbre.gauche est vide et arbre.droit est vide:
        retourner 0
    si arbre.gauche est vide et arbre.droit est non vide:
        retourner 1 + hauteur(arbre.droit)
    si arbre.gauche est non vide et arbre.droit est vide:
        retourner 1 + hauteur(arbre.gauche)
    si arbre.gauche est non vide et arbre.droit est non vide:
        retourner 1 + max(hauteur(arbre.droit),hauteur(arbre.gauche))

Parcours d'un arbre

Le parcours d'un arbre correspond à l'ordre dans lequel on parcourt ses nœuds. Voici les différentes façons de parcourir un arbre :

Parcours en largeur

On commence par la racine puis ses fils, puis les fils des fils etc. On avance niveau par niveau et on attend qu'un niveau soit complètement parcouru avant de passer au suivant. Sur chaque niveau, on avance de gauche à droite.

Sur le graphe ci-dessus cela donne : R-G-S-D-K-M-N-B-A-T-U.

Parcours en profondeur

Ici, on visite le sous-arbre gauche avant le sous-arbre droit pour chaque nœud. Il existe trois types de parcours en profondeur en fonction de l'ordre de visite des fils par rapport à leur père.

Préfixe

Père-Filsgauche-Filsdroit. Si filsgauche est également père, on visitera son propre filsgauche avant de passer à filsdroit (c'est le parcours en profondeur).

Sur l'exemple : R-G-D-B-A-K-T-S-M-N-U

Infixe

Filsgauche-Père-Filsdroit.

Avec l'exemple : B-D-A-G-K-T-R-M-S-U-N

Suffixe

Filsgauche-Filsdroit-Père.

Sur l'exemple : B-A-D-T-K-G-M-U-N-S-R.

Exercices

On considère l'arbre ci-dessous :

5) Donner l'ordre des nœuds pour un parcours en largeur.

6) Donner l'ordre des nœuds pour un parcours en profondeur préfixe.

7) Donner l'ordre des nœuds pour un parcours en profondeur infixe.

8) Donner l'ordre des nœuds pour un parcours en profondeur suffixe.

9) Donnez le type de parcours d'arbre des algorithmes suivants :

parcours1(nœud):
    si nœud non vide:
        parcours1(nœud.gauche)
        affiche(nœud.valeur)
        parcours1(nœud.droit)

parcours2(nœud):
    si nœud non vide:
        affiche(nœud.valeur)
        parcours2(nœud.gauche)
        parcours2(nœud.droit)

VARIABLES
f : file

DEBUT
parcours3(nœud):
    f.enfile(nœud)
    tant que f est non vide:
        x = f.defile()
        affiche x.valeur
        si x.gauche non vide:
            f.enfile(x.gauche)
        si x.droit non vide:
            f.enfile(x.droit)
FIN

parcours4(nœud):
    si arbre non vide:
        parcours4(nœud.gauche)
        parcours4(nœud.droit)
        affiche(nœud.valeur)

On considère maintenant l'arbre ci-dessous :

10) Donner l'ordre des nœuds pour un parcours en largeur.

11) Donner l'ordre des nœuds pour un parcours en profondeur préfixe.

12) Donner l'ordre des nœuds pour un parcours en profondeur infixe.

13) Donner l'ordre des nœuds pour un parcours en profondeur suffixe.