Exercices (pc 5)

Exercice 1 : Donner une fonction (d’abord récursive puis non-récursive) de parcours préfixe d’un arbre représenté par deux tableaux F g, F rd donnant pour chaque noeud son fils gauche et son frère droit. On pourra utiliser aussi le tableau P qui donne le père d’un noeud.

Exercice 2 : Mêmes questions pour un arbre binaire représenté par les tableaux F g, F d donnant les fils gauche et droit.

Exercice 3 : Montrer qu’il existe une bijection entre les ensembles suivants:

1. Les arbres binaires à n noeuds.

2. Les arbres binaires complets à n + 1 feuilles.

3. Les arbres planaires à n + 1 noeuds.