Chapitre 6 : Arbres binaires

Illustration d'un arbre

---

Exemple

\((3+2) \times (5-4)\)

---

Définition

Un arbre binaire étiqueté (par des entiers) est

• Soit l’arbre vide (vide)
• Soit « l’assemblage »
  • De 2 arbres
  • Et d’un entier

A := (vide) | (A,A,I)

Avec I : l’ensemble des entiers.

A : l’ensemble des arbres binaires étiqueté par des entiers.

Que contient A ?

---

(vide,vide,42) :

---

(vide, (vide,vide,42),1) :

---

((vide,vide,42),(vide,vide,42),3) :

---

Vocabulaire :

Taille : \(6\)

Hauteur : \(4\)

---

Si un arbre binaire est de hauteur \(h\), alors il possède au plus \(2^h -1\) nœuds.

Les nœuds qui ne sont pas des feuilles sont appelés nœuds internes.

• La taille d’un arbre est son nombre de nœuds
• La profondeur d’un nœud est le nombre de nœuds rencontrés par un chemin élémentaire allant de ce nœud à la racine.
• La hauteur d’un arbre est le maximum des profondeurs de ses nœuds s’il est non vide et 0 s’il est vide.

Pour un arbre complet, le nombre de noeuds a une profondeur \(p\) est : \(2^p\).

---

En C :

typedef struct_noeud_t{
    int v;
    struct_noeud_t* g;
    struct_noeud_t* d;
} noeud_t;

//l’arbre vide sera représenté par la valeur NULL

---

Exemple :

noeud_t* allN(int pv, noeud_t* pg, noeud_t* pd){
    noeud_t* r = (noeud_t*) malloc(sizeof(noeud_t));
    if (r == NULL){
        printf("erreur d’allocation\n");
        exit(1);
    }
    r->v = pv;
    r->g = pg;
    r->d = pd;
    return r;
}

---

Parcours en profondeur d’un arbre

Un parcours est une façon de le représenter sous la forme d’une chaine de caractères.

Parcours_prefixe(A) :

• Si A est vide on affiche V
• Sinon
  • On affiche l’étiquette de la racine de v
  • Parcours_prefixe(sous-arbre à gauche de la racine)
  • Parcours_prefixe(sous-arbre à droite de la racine)

---

Il existe d’autres types de parcours en profondeurs.

• Parcours post-fixe (ou suffixe)

  • gauche
  • droite
  • racine

• Parcours infixe

  • gauche
  • racine
  • droite