dynamic data structures - cpt

Write a program that contains a set of routines (methods) for manipulating a personal phone directory (you will need to use files here). The directory should be maintained as a binary search tree with each node containing a reference to an object containing fields for a family name, a given name, an address and a telephone number. The tree's nodes should be ordered using family names as keys. If there are entries with identical family names, given names should be used a secondary keys. No entry will have identical family and given name. The program should be menu driven with the user being offered a choice of six [6] commands only:

  Insert a new entry in the directory. The program should prompt the user for a new name, address, telephone number and insert the new entry in the tree. If the new name is already in the list, an error message should be produced and the new item is not entered in the tree.

  Delete an entry from the directory. Prompt the user for the name to be deleted, then delete that entry. If this proves to be difficult, you could have a field in each node indicating whether the node has been deleted. This could be a boolean field. When the node is created, this field is set to true. To delete, reset this field to false.

  Search for a (user-supplied) name in the directory. The program should print the name, address and telephone number of the entry or an error message if the entry is not found.

  Edit an entry. The user should supply a family name and given name and the program will then prompt the user to provide new information for the address fields and/or the telephone number field.

  Print the list, in alphabetical order by family name, in a file.

  Quit the program, saving the current directory entries in a file. Given the Quit command, the program should save the data using a pre-order traversal of the tree. This will allow you to reconstruct the tree in the form that it had before being saved. On giving the Quit command, the user should be able to specify the name of the file into which the data should be saved. When you quit the program, you should save only the "non-deleted" nodes. This might disturb the structure of the tree to some extent but not much. On starting the program, the user should be given the option of either starting with an initially empty tree or retrieving an existing directory from a file whose name is specified by the user.

  Due: Tuesday May 5 @ midnight. Submit one file only.