Topics: Binary Search Trees - Theory and Practice
The assignment is in two parts. In Part 1, you code and test the binary search tree operations. Part 2 consists of exercises on binary search trees.
How to Test. You will test your tree operations on files I provide, containing commands to invoke the various tree operations. These operations are:
|c||construct an empty tree (done in the command interpreter)|
|i key||insert node with key key into the tree|
|d key||delete node with key key from the tree|
|s key||search for node with key key in the tree|
|P|| Print the keys
horizontally using an inorder tree walk |
|S||Show (display) the actual tree structure|
|#||echo the comment line|
Initially in the command interpreter constructs an empty tree on which all subsequent operations will be performed. The 'i' and 's' commands work just as described in Chapter 12. The 'd' command is a bit different, having a key as an argument rather than a pointer (to implement this, first do a Tree-Search for the key, which returns a pointer x, and then call Tree-Delete with x as an argument). The key parameter is just a positive integer. For simplicity we ignore any satellite data fields. The 'P' command prints the keys in order horizontally doing an in-order tree walk. The 'S' command, discussed below, Shows the tree structure. Finally, a line beginning with a '#' the line is interpreted as a comment and simply echoed to standard output. Lines beginning with any other character are ignored.
As in a previous assignment, you need to provide a simple command interpreter to read and parse these commands. It need not be super robust and full of features; it only needs to be able to minimally interpret these commands and dispatch control to the appropriate procedure. You might want to start with a command interpreter you used for a previous assignment. As before, the code for this interpreter should be in a separate module from the code for your binary search tree operations.
A Test Example. The following is an example of a set of test
|# create tree|
|# insert 10 items|
|# Print nodes in order|
|# Search for 474 and 817|
|# Show tree structure|
|# Delete 372 and 555|
|# Show structure again|
+-------------------------------------------------+ |# create tree (done in command interpreter) | |# insert 10 items | |# Print nodes in order | | | |122 125 245 372 418 440 474 491 752 934 | | | |# Search for 474 and 817 | | | |Search key 474 found | | | |Search key 817 not found | |# Show tree structure | | | |Structure of tree (rotated 90 degrees to left): | | | | 934 | | 752 | | 491 | | 474 | | 440 | | 418 | | 372 | | 245 | | 125 | | 122 | | | |# Delete 372 and 555 | | | |Search key 555 not found | |# Show structure again | | | |Structure of tree (rotated 90 degrees to left): | | | | 934 | | 752 | | 491 | | 474 | | 440 | | 418 | | 245 | | 125 | | 122 | +-------------------------------------------------+Notice that informative messages are given by the search operation, and also by the delete operation when the key to be deleted is not found.
For the tests that you hand in, commands will be processed in batch mode (i.e., read from files). However, you may want to design the command interpreter so that it can read commands from standard input as well so that you can more conveniently test simple operations in the early stages.
Displaying The Structure Of The Tree.
You can use recursion to display the structure of the tree if the
tree is oriented on the page (or screen) with the root at the far left
and children to the right. The algorithm is:
ShowTree(x, depth) |> x points to root of subtree with given depth
if x not = NIL
then ShowTree(right[x], depth+1)
print key[x] right-justified in a field of (depth * 6) + 4
The procedure is originally called with
Helpful skeleton code:
Here is a
a "command interpreter"
(note the commented-out stuff, which will be useful later),
a .h file for the BST class
and skeleton code for the BST class implementation
When you download these files, be sure to remove the ".txt" suffixes
(by moving them to the same file name without the ".txt").
What To Hand In. Hand in typescripts like the one given above for the test files: