Profondeur Première recherche: Soit un ensemble de lettres construire des mots valides

Question

Disons que j'ai un ensemble de lettres {a, b, c, t} et un dictionnaire de fonction (s) qui retourne T/F pour vérifier si une chaîne s existe dans le dictionnaire anglais. Construisez des mots valides en utilisant la recherche approfondie en profondeur.

Je ne demande pas de code ici. J'ai besoin d'aide avec la structure de l'arbre. Je ne suis pas capable de visualiser la structure de l'arbre dans ce problème.

Par exemple, ces quatre lettres peuvent être dans une seule colonne pour s DFS. Alors dois-je construire l'arbre pour toutes les permutations possibles et ensuite effectuer un DFS?

Edit: je dois construire des mots de taille 3.

Exemple:

 a    b 
    /   /
     b    c 
    /   /
    c    t 
/   /
    t    a 

Answer 1

Structure Arbre:

Vous pouvez construire un arbre à chaque noeud représentant une lettre dans la alphabet. Un noeud serait potentiellement lié à toutes les lettres de l'alphabet.

Dicitionary de charge:

mots de charge et construire arbre. Chaque lettre du mot nous ferait marcher à travers l'arbre à partir de la racine. Si nous frappons un null dans l'un des liens, puis créer un nouveau nœud.

Utilisation:

Ensuite, il suffit automne à travers le premier lien jusqu'à ce que vous frappez un drapeau endOfWord, ce qui signalerait un mot.

typedef struct { 
    char *letter[ 26 ]; 
    bool endOfWord; 
} 

Le nœud racine serait nul comme point de départ.