[TP 1 : Arbres binaires ](https://mybinder.org/v2/gh/fortierq/binder-mp2i/main?urlpath=git-pull%3Frepo%3Dhttps%253A%252F%252Fgithub.com%252Fmp2i-info%252Fmp2i-info.github.io%26urlpath%3Dlab%252Ftree%252Fmp2i-info.github.io%252F5_arbre%252Ftp_td%252Ftp1_arbre_binaire.ipynb%26branch%3Dmain)

On écrira 2 versions pour chaque fonction : en OCaml et en C.

Pour écrire du code en OCaml et C, on pourra

• soit utiliser SoS et sélectionner le langage pour chaque cellule
• soit utiliser 2 notebooks : un en OCaml, l'autre en C

Définitions¶

Exercice

Redéfinir deux types d'arbres binaires : en C et en OCaml (si possible sans regarder le cours).

Exercice

Définir l'arbre suivant, en C et OCaml. On pourra l'utiliser pour tester les réponses dans les exercices suivants.

Nombre de feuilles¶

On rappelle qu'une feuille est un noeud sans fils (dont les deux sous-arbres sont vides) et qu'un noeud interne est un noeud qui n'est pas une feuille.

Exercice

Écrire une fonction n_leaf renvoyant le nombre de feuilles d'un arbre binaire. Revoir les fonctions sur les arbres écrites en cours, si besoin.

Un arbre est binaire strict si ses noeuds ont 0 ou 2 fils.

Exercice

Soit $a$ un arbre binaire strict. Conjecturer une formule reliant le nombre $f(a)$ de feuilles de $a$ avec son nombre $n(a)$ de noeuds internes, puis la prouver par récurrence.

Profondeur maximum¶

Question : Écrire une fonction max_depth renvoyant la profondeur maximum d'un arbre binaire, en complexité linéaire.

Diamètre¶

Exercice

1. Rappeler la définition de la hauteur $h(a)$ d'un arbre binaire $a$, sous forme de relation de récurrence.
2. Écrire une fonction pour calculer la hauteur d'un arbre binaire.

Le diamètre $d(a)$ d'un arbre $a$ est la longueur maximum d'un chemin entre 2 noeuds quelconques de cet arbre. Par exemple, le diamètre de l'arbre en exemple est $5$, correspondant au chemin $4 \rightarrow 3 \rightarrow 1 \rightarrow 0 \rightarrow 5 \rightarrow 7$.

Exercice

:

1. Soit $a$ un arbre binaire composé d'une racine, d'un sous-arbre gauche $g$ et d'un sous-arbre $d$. Donner, en la démontrant, une relation permettant de calculer $d(a)$ en utilisant $g$ et $d$. On pourra utiliser la $h(g)$ et $h(d)$.
2. En déduire une fonction permettant de calculer le diamètre d'un arbre binaire. Quelle est sa complexité ?
3. Améliorer la fonction précédente pour calculer le diamètre en complexité linéaire.

Arbre binaire complet¶

Exercice

Écrire une fonction ayant un entier $h$ en argument et renvoyant un arbre binaire complet de hauteur $h$ avec que des $0$ comme étiquettes.