Return to Coding in Java with artEoz – exercises

N-ary trees

An n-ary tree is a tree in which each node has any number of son. One can use an n-ary tree to represent a dictionary and thus speed up the search. The root has as many son as possible first letters, then each son has as many son as possible second son letter, and so on. To represent such a tree, one solution is to attach two links to each node: a link to its first son and a link to its brother.

  1. Make sure you have the arbre resource. If necessary, see the Resources import webpage.
  2. The Dictionnaire class provides a constructor with no parameter. How many fields are needed to represent an instance of this class? key_48
  1. The void ajouter(String) function adds a word in the dictionary. Add the word BU in the dictionary and check the evolution of memory diagram. What happened ? key_48
  2. What happens if you add a new word starting with a different letter, such as AIR?
  3. What happens if you add an existing word again, as BU or AIR? key_48
  4. To be sure you understand what is happening, add a third word beginning with another letter. Choose a short word to avoid cluttering the diagram. What is going on ? key_48
  5. The function boolean contient(String mot) verify the ownership of a word to the dictionary. How many Node instances will be explored during the search of the word AIR? key_48
  6. What happens now if we add a word that begins with a letter already registered, BOL for example? key_48
  7. Carefully follow what happens if we add a new word as BON.
  8. After all these additions, does the membership test of the word AIR require as much or more exploration of nodes? key_48