Automated Binary Search Tree Phone Book
In this assignment we will remove the circular linked list that we used in our previous programming assignment to implement a phone book and substitute a binary search tree. The binary search tree gives more efficient access to phone book records.
The phone book will be written to a disk file called PB.dat using a preorder traversal when the user indicates he/she want to exit. The program will read PB.dat into a BST when the program loads. This enables us to have a permanent phone book; not one that disappears when the program terminates. Using a preorder traversal to write the phone book ensures that when the phone book is loaded into memory the binary tree has the same structure that it had when written to disk.
Once again, the phone book driver program will not manipulate nodes or pointers directly. It will rely upon member functions of the binary tree to add and delete information and navigate through the storage structure (binary search tree).
You may receive extra credit on this program in a number of ways but first write and test the basic program. One important and not-too-difficult enhancement is to move the class declaration and all member functions to an object library and accompanying .h file so that the main program will contain only the driver program.
The declaration of the binary tree is of critical importance in this assignment. You will find many implementations of binary trees in text books but, probably, not one quite like this one. We will base our declarations on one common definition of a binary tree. I.e., a binary tree has 0 or more nodes; one of which is designated as the root. Each node has three components, left and right, that represent binary search subtrees and a data component. A difference in a simple binary tree and a binary search tree is that the binary search tree has the property that the stored data contains a key value such that the key value in the root of the left subtree is less than the key value in the root of the tree. And the key value in the root of the right subtree is greater than or equal to the key value in the root of the tree.
In the above definition you should be able to identify at least four concepts.
- The binary tree
- The root of the binary tree
- Binary tree nodes (including the data stored in the node and a left and right subtree)
- A key value in the data
Our implementation will define a BST class that will contain the root of the binary search tree. It will also define a btnode class that will define a binary tree node. Ideally you should define a third class BSTMgr (binary search tree manager) whose function is similar to the list manager class we created for the circular linked list. Alternatively you may put a single current pointer in the BST class. The purpose of the current pointer is to encapsulate the current node into the tree definition/class so that the driver program will never need to manipulate pointers. This enables us to keep the driver independent of the underlying phone book data structure implementation. Having a separate bt manager class enables us to have more than one current access point into the BST. Additionally we will incorporate a parent component that will be a pointer to a node's parent node. Although not strictly necessary the parent pointer facilitates certain binary tree operations.
You may wish to review the lab
that we completed in class that defined such a binary search tree and a simple driver program. The program that you must complete will be more complex than this lab but will share nearly the same data declarations. The lab is just intended to get you started but taken together with the circular linked list implementation of the phone book should give you most of what you need for this program.
Some of the most important functions that you will need are the following:
- create a new BST
- determine if the BST is empty
- detemine if a node is a leaf.
- move to first element in the BST
- move to next element in the BST
- add an element to the BST
- find an element in the BST
- delete the current element from the BST
- return the info in the current element of the BST
The phone book will present the user with a menu that enables the user do perform the following.
- create a new phone book
- determine if the phone book is empty
- move to first element in the phone book
- move to next element in the phone book.
- add an entry to the phone book
- delete an entry from the phone book
- change phone number of current entry
- find an entry in the phone book
- display the current element in the phone book
- list the entire phone book
- read a phone book in from a disk file
- write a phone book to a disk file
Again, we recognize three high-level concepts.
- The phone book
- The structure in which to store the phone book (i.e., the implementation of the phone book). This supports the required phone book operations.
- The underlying physical data structure that supports the conceptual data structure that implements the phone book.
It is important to make these distinctions to support conceptual independence.
I.e., the phone book will define functions/methods it requires in order to properly function as a phone book. A binary search tree will support these functions of the phone book. The implementation of the lower-level structure will actually manipulate low-level C++ constructs such as pointers or arrays.
Lower-level constructs should not be aware of the higher-level contructs that might use them and higher-level constructs will only be aware of the construct immediately below it. So, for example, the phone book itself will be completely independent of the lowest level data structure implementation.
Toward this end we have one troublesome problem to deal with - i.e., the data stored in the nodes. The basic problem is that the data should only be meaningful to the phone book itself. However, searching the phonebook may require being aware of the structure of the binary search tree. There are several potential solutions to this problem. Here is one that is not difficult to implement.
The data in the nodes will always be a pointer to a string of characters. The phone book may require as many fields as it likes but it will always pack them into a single string before asking that they be stored in the phone book. The BST will only know that the data is a string of characters and will return that string when requested by the phone book. The phone book is responsible for unpacking the data into its requisite fields.
This still leaves the problem of searching for a node since the search is based upon a key field not necessarily the entire data. Since we are implementing a binary search tree; not simply a binary tree it is logical to define a key within the tree. However, the starting position and length of the key must definable by the driver application. This may be implemented by defining in the BST class two integer fields representing the starting position and length of the key and a function that the driver program can call to give these fields values.
A workable alternative is to incorporate a key field and a data field into the node definition. There are advantages and disadvantages to this approach. Either is acceptable.
Thus the BST will be able to search itself for a node with a particular key value and still have a structure that is independent from the driver program.
You will notice that we dealt with data key value independence issue in our lab program by using a key field and a data field. This was intentional in order to simply the coding of a short lab.
Top of this page 
Home page 
