TP 3 : Arbres

Encore des arbres binaires¶

On rappelle les définitions d'arbres binaires en C et OCaml :

In [2]:

type 'a btree =
    | E (* arbre vide *)
    | N of 'a * 'a btree * 'a btree;;

type 'a btree = | E (* arbre vide *) | N of 'a * 'a btree * 'a btree;;

Out[2]:

type 'a btree = E | N of 'a * 'a btree * 'a btree

In [3]:

typedef struct btree {
    btree *g;
    btree *d;
    int val;
} btree;

typedef struct btree { btree *g; btree *d; int val; } btree;

Warning in cling::IncrementalParser::CheckABICompatibility():
  Possible C++ standard library mismatch, compiled with __GLIBCXX__ '20200312'
  Extraction of runtime standard library version was: '20210601'

In [4]:

btree* make_node(int r) {
    btree *t = (btree*)malloc(sizeof(btree));
    t->g = t->d = NULL;
    t->val = r;
    return t;
}

btree* make_node(int r) { btree *t = (btree*)malloc(sizeof(btree)); t->g = t->d = NULL; t->val = r; return t; }

On écrira, si possible, chaque fonction en C et OCaml.

Exercice

Écrire une fonction pour renvoyer la somme des éléments d'un arbre binaire.

Exercice

Écrire une fonction appartient déterminant si un élément appartient à un arbre binaire. Quelle est sa complexité?
Remarque : Il sera plus simple de faire un test d'appartenance avec un arbre binaire de recherche.

Exercice

Écrire une fonction pour savoir si deux arbres binaire sont égaux. Quelle est sa complexité?

Exercice

Écrire une fonction pour savoir si un arbre binaire est strict (c'est-à-dire : si tous les noeuds ont $0$ ou $2$ fils).

Arbres quelconques¶

Dans cet exercice, on répondra d'abord à toutes les questions en OCaml, puis en C, en ayant défini un type qui convient.

Dans le cas général, un arbre peut avoir un nombre quelconque de fils. En OCaml, on peut utiliser une liste pour les fils :

In [1]:

type 'a tree = N of 'a * 'a tree list

type 'a tree = N of 'a * 'a tree list

Out[1]:

type 'a tree = N of 'a * 'a tree list

In [6]:

let t = N(0, 
          [N(1, 
             [N(2, []);
              N(9, []);
              N(7, [])]);
           N(3, []);
           N(5,
             [N(6, []);
              N(7, [])])
          ])

let t = N(0, [N(1, [N(2, []); N(9, []); N(7, [])]); N(3, []); N(5, [N(6, []); N(7, [])]) ])

Out[6]:

val t : int tree =
  N (0,
   [N (1, [N (2, []); N (9, []); N (7, [])]); N (3, []);
    N (5, [N (6, []); N (7, [])])])

Exercice

Écrire une fonction pour renvoyer la hauteur d'un arbre quelconque.

Exercice

Écrire une fonction pour renvoyer le nombre de feuilles d'un arbre quelconque.

Il est possible de représenter un arbre quelconque $t$ en arbre binaire $t'$ où chaque noeud $n$ de $t'$ est de la forme $n = N(r, g, d)$ où $g$ est le premier fils (le plus à gauche) de $n$ dans $t'$, et $d$ est le prochain frère de $n$ dans $t$. Ainsi, l'arbre ci-dessous est transformé en l'arbre binaire suivant :

Exercice

Écrire une fonction pour transformer un arbre quelconque en arbre binaire.