Description
1 Introduction
In this assignment, you’re going to write a program that builds a database of license plates and names using a binary search tree (BST). After reading in a le containing plate/name pairs, your program will let the user enter a license plate, and it will display the corresponding name. The user can also enter commands instead of a license plate, in order to further interact with the BST.
2 Behavior
You should run /tmp/plate4 (you can use /tmp/database.txt as a sample database) to observe the following behaviors. Your program’s output and other behavior should match that sample program as closely as possible. Minor variations ( PLATE NOT FOUND vs Plate not found for example) are ne, but anything other than minor cosmetic di erences will cost points.
2.1 Start-up
Your executable program must be named plate and be run as:
- plate database_name
Your program should report an ERROR if it is not run correctly, and then return(1).
2.2 Reading the database
Once the program begins, it should open the database for reading and ingest data, one line at a time, building a BST from the data (keyed on plate). The data looks like this:
PTN-673 RICHELLE MUELLER
QFJ-481 LUDIVINA WOODWARD
RRW-885 VITO HUBBARD
and so on. Each line contains a license plate ID (no spaces, but make no other assumptions about the format), followed by a space, a rst name, a space, a last name, and a newline (\n). If the database cannot be read, the program should report an ERROR and return(1).
2.3 User Interaction
The program then prompts the user to enter a license plate or a command. If a plate is entered, it should search the BST and either print the name associated with the plate, or print the message Plate not found. If the user enters a command, it should execute the command. In any case, the program will repeatedly prompt the user and process their commands.
2.3.1 Legal Commands
There are two commands the user can enter:
*DUMP
This will display information about the tree (see below)
*DELETE plate
This will delete the given plate from the tree using the exact algorithm discussed in class. Make sure you understand this algorithm (which is not the same as you’ll nd online): any variation from it will result in loss of points.
2.3.2 Output Details
Normal plate information (in response to a plate look-up) should be printed as follows:
Enter command or plate: BLD-947
First name: ELIZ Last name: FRANKLIN Enter command or plate:
The *DUMP command should report the following information (in this exact order and format):
TREE HEIGHT: 7 (or whatever)
BALANCED: (YES or NO)
| LNR TRAVERSAL: | |
| Plate: <AOG-380> | Name: YATES, DORETTA |
| Plate: <BVJ-347> | Name: FINCH, SHELTON |
| Plate: <MOQ-693>
(… and so on) |
Name: MYERS, INDIRA |
NLR TRAVERSAL:
(show that data)
LRN TRAVERSAL:
(show that data)
Enter command or plate:
Please avoid extra output, changing the order of the output, etc.
The *DELETE command should either report SUCCESS or PLATE NOT FOUND
2.4 Exiting
The user exits the program by entering EOF (CTRL-D at the beginning of a line). This is the only way your program should exit: it should not exit in response to errors, and it should not seg fault. Before exiting, the program should free all memory that it allocated.
3 Implementation
You will implement a BST whose nodes are as follows:
struct node{ char *plate; char *first; char *last; struct node *left; struct node *right;
}; typedef struct node* Node;
Remember that there is no sentinel associated with a BST. In your main program, your tree can be declared as
Node root=NULL;
to represent your initial (empty) tree.
Note that you cannot assume pre-de ned sizes of the struct node’s strings: plate, rst and last could be 2 characters, 20 characters, or anything else. Therefore, you will be using malloc to allocate memory for the nodes of the BST, and for the contents (3 strings) of those nodes.
Remember to free all malloc’d memory before exiting.
4 DETAILS
4.1 Required Functions
Implement the following functions, for use from your main program:
| int height(Node root); | // return height of tree |
| int balanced(Node root); | // 1= means tree is balanced, 0 means tree is not balanced |
Node add(Node root, char *plate, char *first,
char *last); // Add a node to the tree and return the (new?) root of the tree
int search(Node root, char *plate, char *first,
char *last); // search for plate; if found, populate first and last and return 1
// if not found, return 0 and don’t change first or last
Node delete(Node root, char *plate); // search for plate, and if found, delete it // return the (new?) root of the tree
void LNR(Node root); // print tree contents in LNR order (formatted as described above) void NLR(Node root); // print tree contents in NLR order (formatted as described above) void LRN(Node root); // print tree contents in LRN order (formatted as described above) void treeFree(Node root); // release all memory associated .
