Arbre lexicographique

Question posée au contrôle continu du 16 juin 1997

On veut construire un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de sorte que les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte des accents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à ce noeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai).

Sur la base des déclarations suivantes, écrivez une procédure imprimant touts les mots du dictionnaire dans l'ordre croissant de longueur de mot et, pour des mots d'une même longueur, par ordre alphabétique:

type VersNoeud= ^Noeud;
     Noeud= record
              Desc: array['a'..'z'] of VersNoeud;
              Complet: boolean;
              end; { Noeud }

var Dico: VersNoeud;

procedure Imprime(LeDico: VersNoeud);

Note: vous avez intérêt à considérer cet arbre lexicographique comme un graphe orienté et appliquer une des méthodes de parcours de graphe. Vous pouvez aussi considérer, si vous en avez besoin, que vous disposez d'un type "Pile" ou "FileDAttente" avec leurs procédures de manipulation. Vous pouvez aussi utiliser des strings pour réconstituer une séquence de lettres formant un mot.

Solution

Site Hosting: Bronco