(Session 2) In the proposed project during the year, you are asked to write a function that, given a string, returns the number of dictionary words with this string as a prefix (begins with that string).

(Session 1) In the proposed project, answer the following questions:

• Draw the tree of a dictionary that contains the following words: carte, car, char, gain, pain, paix, gage, gare. 
• What is the maximal number of nodes ('$\setminus\,0$' included) in a dictionary tree that may occur at a given level N (Assuming that the root is at level 0) ? Justify your answer.
• Provide the declarations used in the project to represent a dictionary, and write a function that adds a word to the dictionary. 
• Write a recursive function that returns the length of the longest word in the dictionary.

Project description

To perform a spelling checker, we have to quickly test whether a word exists in a dictionary and to be able to add new words. In the case of a relatively dense dictionary, it is interesting to not to repeat common prefixes. Thus, we represent a dictionary by a tree in which each node (except the root) contains a letter. Each word is represented by a path from the root to a leaf. Common prefixes to several words are on the same path. The special character '\0' represent the end of a word.

Example :

The dictionary D = {go, god, game, her, here, bad, box} is represented by the following tree:

Note that words with a common prefix share a part of the defining paths and every word is represented by a path from the root and ending with a leaf containing '\0'.

Thus, the root can have 27 children corresponding to the 26 letters of the alphabet + word-ending character ('\0'). At the second level, each of the 26 nodes (other than '\0') can have 27 children. Thus, we count 26 ´ 27 nodes. One possible representation is by representing each node by an array of 27 characters of which few will be significant. This lead quickly to an explosion of memory since the number of levels corresponds to the length of the longest word in the dictionary. Thus, we choose a pointer based representation corresponding to a planar tree (having multiple children). Each node will contain in addition to the character, a link to its leftmost child (eldest son) and another one to his right brother.

This gives:

typedef struct node{
     char Data ;
     struct node *LeftChild, *RightBrother ;
} *dictionnary;

The previous tree will be represented as follows:

Work to be done

Implement dictionary type with the following basic operations, namely:

• Create a dictionary;
• Add a word;
• Find a word;
• View all dictionary

The question was part of a project !!