Exercices (pc 5)

Exercice 1 : Donner une procédure (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.

Indication: Pour la procédure non récursive, on pourra distinguer deux cas suivant que l’on commence à explorer les descendants du sommet de pile ou que l’exploration du sommet de pile est terminée.

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

1. Les arbres binaires à n noeuds.

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

3. Les arbres planaires à n + 1 noeuds.