On définit sur les arbres de recherche m-aire d’ordre p les types de parcours suivants

inordre : T₁ n₁ T₂ n₂ T₃........n_p-1 T_p

Préordre : n₁ T₁ n₂ T₂ .....n_p-1 T_p-1T_p

Postordre : T₁ T₂ n₁ T₃ n₂ T₄ .......T_p n_p-1

1. Dresser l’arbre de recherche m-aire d’ordre 3 à partir d’une séquence de 20 nombres différents.

2. Donner la liste des éléments pour les 3 types de parcours ainsi définis.

3. Ecrire les modules qui fournissent la prochaine valeur inordre, préordre et postordre de la i-ième valeur d’un nœud d’adresse n donnée. . On utilisera le modèle sur les arbres de recherche m-aire augmenté de l’opération Pere(n).

On utilisera la machine abstraite suivante définie sur les arbres de recherche m-aire :

- Degre(p) : accès au nombre de sous arbres du nœud p.

- Fils (p,1), Fils(p, 2), .....,Fils(p, Degre(p)) : accès aux différents fils.

- Info (p, i )  : Accès à la i-ème information du nœud p

- Aff_degre(p, n) : modifier le champ degré par la valeur n.

- Aff_fils(p, i, j) : faire j le i-ième fils du nœud p.

- Aff_info(p, i, v)  : faire de v la i-ème information du nœud p.

- Creernoeud(p) : allocation d'un nœud. L’adresse de ce nœud est rendue dans p.

- Liberernoeud(p) : libération du nœud référencé par p.