Begin by creating a new project for this week's files. Download tester.cpp, BST_Tester.h, BST_Tester.cpp, BST.h, BST.cpp, and Exception.h. Import these files into your project, open the files, and personalize their opening documentation. Then take a few minutes to look them over, to become familiar with their contents. Save/compile, and run the tests, to verify that everything works correctly at the outset.
As you can see, our BST class contains just two instance variables:
Node* myRoot; // pointer to the first item we insert unsigned myNumItems; // number of items I containIf our BST is empty, then myRoot should have the value nullptr and myNumItems should equal zero.
In BST_Tester.cpp, uncomment the call and definition of testConstructor. Save/compile, and verify that you get compilation errors. Take a few moments to study testConstructor(), to see what you must do to pass it. Modify BST.h and BST.cpp as necessary to fix these errors; then save/recompile.
When your project compiles correctly, run the tests. When your project passes all tests, continue.
Your BST class now provides methods to:
Our next task is to be able to insert items into a BST. The insert(it) method adds an item it to the tree by storing it in a node such that:
A tree's shape can be characterized in different ways. One way is by comparing its height, diameter, and maximum width:
By contrast, if we insert items in ascending order: 11, 22, 33, 44, 55, 66, 77, then our tree will be imbalanced one way:
This tree's height is 7, its diameter is 7, and its maximum width is 1.
Likewise, if we insert the items in descending order : 77, 66, 55, 44, 33, 22, 11, then our tree will be imbalanced the other way:
As before, this tree's height is 7, its diameter is 7, and its maximum width is 1.
In BST_Tester.cpp, uncomment the call to and definition of testInsert(). Save/compile, and verify that you get a compilation error indicating that insert() is undeclared.
Add a prototype of insert() to our BST class; then recompile and verify that only a linking error remains.
In BST.cpp, create a stub for BST::insert(). Recompile, and when all errors have been eliminated, run the test. Then define BST::insert() so that it passes the test. Here is a hint, in case you get stuck, but do your best to build this method without looking at it. Run the project, and verify that everything works correctly at the outset.
Uncomment the definition and call of BST_Tester::testContains(). Take a few minutes to look over the tests it contains, specifically how contains() is used. As can be seen, the contains(it) method returns true if it is in its BST; otherwise it returns false. Save/compile your project. You should see an error indicating that there is no method matching the calls in our test-method.
Modify BST.h and BST.cpp as necessary to fix any complilation/linking errors, using an approach similar to the approach used in insert(). Recompile and run the tests. If you get stuck, here is a hint, but don't use it unless you have to.
Continue when your method passes the test.
To traverse a data structure is to pass through each of its items, processing each item in turn. For example, outputing the values in an array, vector, or list usually involves traversing the structure and outputing each item in turn.
When it comes to binary search trees, there are a variety of ways to traverse a BST:
void BST::traversePreorder() {
if ( !isEmpty() ) {
myRoot->traversePreorder();
}
}
If the BST is not empty, this method "passes the buck" by sending the
traversePreorder() message to the node whose address is in myRoot.
The Node struct defines that (recursive) method as follows:
void BST::Node::traversePreorder() {
// 1. process myItem first (preorder)
processItem();
// 2. then recursively process the items in the left subtree
if (myLeft != nullptr) {
myLeft->traversePreorder();
}
// 3. then recursively process the items in the right subtree
if (myRight != nullptr) {
myRight->traversePreorder();
}
}
The processItem() method can be defined to do any kind of processing of a node's item.
To illustrate, our Node struct defines processItem()
to insert a space and then myItem into cout:
void BST::Node::processItem() {
cout << ' ' << myItem;
}
Uncomment the call and definition of BST_Tester::testTraverse()
and take a moment to look over its tests.
Your final task is to define traversePostorder()
and traverseInorder() methods that will produce the output
expected by the test-method.
Use the provided traversePreorder() method as a model;
the other two traversal methods are quite similar.
When your code passes all the tests, congratulations! You now have a basic binary search tree class!
Copy your project to a new /home/cs/112/current/yourUserName/lab9 folder.
If time permits, you may begin working on this week's project.