6. Arbres : parcours en profondeurs

Cf. TD2

Un arbre enraciné (ou arborescence) est une structure formelle que l’on rencontre dans de nombreuse situations. Les arbres sont souvent représenté avec la racine en haut et les feuilles en bas.

Illustrations

graph TD;
/-->home & proc & dev & foot;
home-->login1 & login2 & key;
login1-->docs & vinte;

Arbre binaire étiqueté par des nombre :

graph TD;
3-->2 & 5;
2-->1;
5-->6 & 20;
20-->7;

Arbre binaire non étiqueté :

On peut caractériser un arbre par une définition récursive :

Définition (arbre binaire non étiqueté, ABNE)

Un ABNE est :

• Soit l’arbre vide.
• Soit l’assemblage de deux arbres (un à gauche et un à droite).

Exemple

Définition (plus symbolique et équivalente) :

Arbre BNE := arbreVide | ArbreBNE * ArbreBNE

Définition (Arbre Binaire étiqueté par des entiers)

Arbre BE := arbreVide | ArbreBE * ArbreBE * ℤ

Exemple

En C

typedef struct noeud {
    int etiquette;
    struct noeud * arbreGauche;
    struct noeud * arbreDroit;
} Noeud;


typedef Noeud * Arbre;

Arbre: a = NULL; // a est l'arbre vide

Parcours d’arbre

Pour représenter un arbre par une liste de mots (ou de nombres).

Parcours en préfixé

• Nommer l’étiquette de la racine de l’arbre ou indiquer si l’arbre est vide.

• Parcourir le sous-arbre de gauche en préfixé

• Parcourir le sous-arbre de droite en préfixe

  • Exemple :
    
    Un parcours préfixé de cet arbre donne : 1\ 3\ 1\perp\perp2\perp\perp7\perp8\perp\perp

  /* On utilise les stuct définit plus haut */
  void parcoursPre(Arbre a) {
      if (a == NULL) {
          printf("Vide");
          return;
      }
      printf("%d ", a -> etiquette);
      parcoursPre((*a).arbreGauche); // même chose, notation différente
      parcoursPre(a -> arbreDroit);
  }
  

On peut *(re)*fabriquer un arbre à partir de son parcours en préfixé.

Parcours en infixé :

• Si l’arbre n’est pas vide :

  • On parcours en infixé le sous-arbre de gauche
  • On écrit l’étiquette de la racine
  • On parcours le sous-arbre de droite

• Sinon :

  • On écrit “vide”

Exemple

Un parcours infixé de cet arbre donne : \perp 2 \perp 1 \perp

Un parcours infixé de cet arbre donne : \perp 2 \perp 1 \perp
==> Deux arbre différents peuvent donner le même parcours infixé.

Parcours suffixe

• Sous-arbre de gauche
• Sous-arbre de droite
• Afficher l’étiquette de la racine