Data structure and alogorithm

--- title: 'Assignment 11: Binary Search Trees' author: 'COSC 2336: Data Structures and Algorithms' date: 'Fall 2020' --- # Objectives - Practice recursive algorithms - Learn how to construct a binary tree using pointers/linked nodes - Learn about binary tree traversal # Description In this assignment you will be given the beginning of a `BinaryTree` implementation using linked nodes via pointers. You will be implementing some of the basic function of a `BinaryTree` abstract data type. The abstraction we are using for the `BinaryTreeNode` and the `BinaryTree` are similar to the Shaffer BSTNode (pg. 156,161) and the BST abstract class and linked pointer implementation (Shaffer pg. 171), but we will define our own version and simplify some of the functions and interface. You have been given a `BinaryTree.[cpp|hpp]` file that defines the `BinaryTreeNode` structure and `BinaryTree` class. This class is current not templatized, the constructed trees only hold items of simple type int (one of the extra credit opportunities suggests you templatize your resulting class). The `BinaryTree` has a constructor, and you have been provided a `tostring()` method and an overloaded `operator<<()` so that you can display the current contents of the tree. # Setup For this assignment you will be given the following files: | File Name | Description | |--------------------|-----------------------------------------------------| | `assg11-tests.cpp` | Unit tests for the member functions and queue | | | functions you are to write. | | `BinaryTree.hpp` | Header file for the BinaryTree class that | | | that you are to add function prototypes for the | | | new member functions into. | | `BinaryTree.cpp` | Implementation file, the implementation of the | | | BinaryTree class member methods for this assignment | | | go here in this file. | Set up a multi-file project to compile the `.cpp` source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. The general approach you should take for this assignment, and all assignment is: 1. Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing. 2. For this project, start by uncommenting the first `TEST_CASE` in the `assg11-tests.cpp` file. These are the unit tests to test the functionality of your `BinaryTree` `insert()` function, the class recursive method you are to implement. 3. Add the `insert()` public and private prototypes to the `BinaryTree.hpp` header file. 4. Add a stub for your two `insert()` member function to the `BinaryTree.cpp` implementation file. The public `insert()` is a void function so it can initially be empty. The private version of the function should return a pointer to a `BinaryTreeNode`, so you should create a new node and return it initially from this function. 5. Your code should compile and run now. Make sure after adding the public and private stub methods your code compiles and runs. However, your unit tests will be failing initially. 6. Incrementally implement the functionality of your `insert()` member functions. Most of the work is actually done by the private `insert()` function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach. 7. Once you have the `insert()` member function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some functions use previous ones in this assignment, so do them in the order given for you in the tasks below. # Tasks You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment: 1. In order to test your class, we first have to get a working capability to insert new items into the `BinaryTree`, which isn't the simplest task to start with, but we can't really test others until we can add new items. For many of the functions in this assignment, you will be required to implement them using a recursive function. Thus many of the functions for your `BinaryTree` will have a public function that asks as the interface that is called by users of the `BinaryTree`, and a private version that actually does the work using a recursive algorithm. I will give you the signature you need for the `insert()` functions: ```c class BinaryTree { private: BinaryTreeNode* insert(BinaryTreeNode* node, const int item); public: void insert(const int item); } ``` Lets start first with the public `insert()` function. This function is the public interface to insert a new item into the tree. Since we are only implementing a tree of `int` items, you simply pass in the `int` value that is to be inserted. This function basically only needs to call the private `insert()` function, passing in the current `root` of the tree as the first parameter, and the `item` to be inserted as the second parameter. Notice that the private `insert()` returns a pointer to a `BinaryTreeNode`. The private `insert()` function is a recursive function. The base case is simple. If the node you pass in is `NULL`, then that means you have found the location where a new node should be created and inserted. So for the base case, when `node` is `NULL` you should dynamically create a new `BinaryTreeNode` item, assign the item and make sure that the `left` and `right` pointers are initialized to `NULL`. When you create a new node like this, you should return the newly created `BinaryTreeNode` as a result from the `insert()` function (notice that the private `insert()` should always return a `BinaryTreeNode*`). This is because, when a new node is allocated, it gets returned and it needs to be assigned to something so it gets inserted into the tree. For example, think of what happens initially when the `BinaryTree` is empty. In that case the `root` of the tree will be `NULL`. When you call the recursive `insert()` on the initially empty tree, you need to assign the returned value back into `root` in the non-recursive function (and you also need to increment the nodeCount by 1 in your public non-recursive function). The general cases for the recursion are as follows. Since we are implementing a binary search tree, we need to keep the tree organized/sorted. Thus in the general case, remember that we have already tested that the `node` is not `NULL`, thus there is an `item` in the `node->item`. So for the general case, if the `item` we are inserting is less than or equal to `node->item`, then we need to insert it into the `left` child subtree (it is important to use `<=` comparison to determine if to go left here). To do this you will basically just call `insert()` recursively with the `item` to be inserted, and passing in `node->left` as the first parameter. Of course, in the case that the item is greater than the one in the current `node`, you instead need to call `insert()` on the `node->right` child subtree. And finally, make sure you take care of correctly returning a result from the recursive `insert()`. Here when you call `insert()` on either the `left` or `right` child subtree, the function should return a `BinaryTreeNode*`. For example, imagine that you are inserting into the `left` child, and there is no `left` subtree, and thus `left` will be `NULL`. In that case the recursive call to `insert()` will create a new node dynamically and return it. So the return value from calling `insert()` needs to be assigned back into something. If you are calling `insert()` on the `left` child, the returned result should be assigned back into `node->left`, and if you are calling on the `right` child, the returned result should be assigned back into `node->right`. Again this is because when we finally find where the node needs to be linked into the tree, we will do it at either an empty `left` or `right` subtree child. Thus in order to link the newly created node into the tree, we need to assign the returned pointer back into either `node->left` or `node->right` appropriately. And finally, after you call `insert()` recursively in the general case, you do have to remember that you always have to return a `BinaryTreeNode*`. For the base case, when you dynamically create a new node, the new node is what you return. But in the general case, you should simply return the current `node`. This will get (re)assigned when you return back to the parent, but this is fine and expected. To summarize, you need to do the following to implement the `insert()` functionality: - The public `insert()` should simply call the private `insert()` on the `root` node. - In the public `insert()` the return result should be assigned back into `root`. - The public `insert()` is also responsible for incrementing the `nodeCount` member variable. - For the private recursive `insert()` the base case occurs when a `NULL` node is received, in which case a new `BinaryTreeNode` is dynamically created and returned. - For the general case, if `node` is not NULL, then you instead either need to call `insert()` recursively on the `left` or `right` subchild, depending on if the `item` to be inserted is `<=` or `>` the `node->item` respectively. - Don't forget in the general case, that the returned result from calling `insert()` needs to be assigned back into `left` or `right` as appropriate. - And finally, the recursive `insert()` always returns a value, and in the general case you should simply just return the `node` as the result. 2. Next we have a relatively easier set of tasks to accomplish. Once you have `insert()` working and tested, we will implement a function to determine the current `height()` of the tree. You should read our textbook to make sure you know the definition of the height of a tree. `height()` needs 2 functions again, a public function which is the interface, and a private function that is recursive and does the actual work. Both the public and private `height()` functions should be declared as `const` functions, as they do not actually modify the contents of the tree. Both functions return an int result. The public function doesn't have any input parameters, but the private function should take a single `BinaryTreeNode*` as its input parameter. The public `height()` function should be very simply, it should simply call the private `height()` on the root node of the binary tree, and return the resulting calculated height. For the private `height()` function, the base case is that if `node` is `NULL` then the height is 0, so you should return 0 in that case. Otherwise, in the general case, the height is conceptual 1 plus the height of the bigger of the heights of the two subtree children `left` and `right`. Thus to calculate the height for a given `node`, recursive calculate height on both the `left` and `right` children, find the maximum of these two, add 1 to it, and that is the height of the `node`. 3. The third and final task is to implement the `clear()` abstract function. The `clear()` function basically clears out all of the stored items from the tree, deallocating and returning the memory used for the node storage back to the OS. As with all of the functions for this assignment, `clear()` needs both a public function that acts as the interface, and a private recursive version that does all of the work. The implementation of the public `clear()` is almost as simple as the previous `height()` function. The public `clear()` should simply call the private `clear()`, passing in the current `root` of the tree. Both the public and private versions of `clear()` should be `void` functions, they do not return any result or value. The private recursive `clear()` is a void function, as we mentioned, and it takes a single `BinaryTreeNode#` parameter as its input. This function is also relatively rather easy. The base case is that, if `node` is `NULL` then you don't have to do anything, simply return, as you have reached the end of the recursion in that case. For the general case, all you need to do is simply call `clear()` recursively on the `left` and `right` subtree children first. Then after this you can safely call `delete` on the node, because all of the nodes in the two subtree children will have been deleted by the recursion, and now you can safely delete and free up the memory for the `node`. # Example Output Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output. ``` $ ./test =============================================================================== All tests passed (40 assertions in 4 test cases) $ ./test -s ------------------------------------------------------------------------------- test is a Catch v2.7.2 host application. Run with -? for options ------------------------------------------------------------------------------- <basic BinaryTree> test basic BinaryTree functionality ------------------------------------------------------------------------------- assg11-tests.cpp:30 ............................................................................... assg11-tests.cpp:35: PASSED: CHECK( t.size() == 0 ) with expansion: 0 == 0 ... output snipped ... =============================================================================== All tests passed (40 assertions in 4 test cases) ``` # Assignment Submission A MyLeoOnline submission folder has been created for this assignment. For these assignments I do not need the test files, nor do I need your visual studio project files or a whole zip/archive of your project directory. For this assignment you have 2 files to submit: `BinaryTree.hpp`, `BinaryTree.cpp`. These should be the only files you added code into (besides uncommenting tests in the test file). Also make sure that the names are the same as originally given to you (do not rename them Assignment or Program01, etc., do not change assg to Assg, make sure the case of the file names is CamelCaseNotation). A large portion of your programs will be tested automatically, so keeping the files names the same and making sure your code passes the unit tests as given to you is important for being able to grade your submission. A MyLeoOnline submission folder has been created for this assignment. There is a target named `submit` that will create a tared and gziped file named `assg02.tar.gz`. You should do a `make submit` when finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment. ``` $ make submit tar cvfz assg11.tar.gz assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp ``` # Requirements and Grading Rubrics ## Program Execution, Output and Functional Requirements 1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied. 1. (40 pts.) `insert()` functionality is implemented correctly. Base and general cases are written as described. Functions work for trees with items and when tree is empty. 1. (30 pts.) `height()` functionality is implemented correctly. Correctly implement stated base and general cases using recursion. 1. (30 pts.) `clear()` functionality is implemented correctly. Correctly implement stated base and general cases using recursion. 1. (10 pts. extra credit) Of course it is not really useful to have a `BinaryTree` container that can only handle `int` types. Templatize your working class so it works as a container for any type of object. You should rewrite the unit tests to use your template class, and submit your rewritten tests. You will need to modify your header and Makefile build to build using a template rather than a separately compilable file. If you do this, submit your code first of the working non-templatized `BinaryTree.[hpp|cpp]` files. 1. (5 pts. extra credit) Implement a `printTree()` method. The `tostring()` method I gave you doesn't really show the structure of the tree. Of course if you had a graphical environment you could draw a picture of the tree. But if you only have a terminal for output, you can display the tree as a tree on its side relatively easy. To do this, you need again both a public and private `printTree()` method. The private method is the recursive implementation, and as usual it takes a `BinaryTreeNode*` as a parameter, and a second parameter indicate the offset or height of this node in the tree. If you perform a reverse preorder traversal of the tree, spacing or tabbing over according to the tree height, then you can display the approximate structure of the tree on the terminal. Recall that preorder traversal is performed by visiting left, then ourself, then our right child. So a reverse preorder is performed by first visiting our right, then ourself, then our left child. 1. (10 pts. extra credit) The `BinaryTree` is missing a big piece of functionality, the ability to remove items that are in the tree. You can read our textbook for a description of how you can implement functions to remove items from the tree. It is a good exercise, and quite a bit more challenging than the `insert()`. The simplest case is if you want to remove a node that is a leaf node (both `left` and `right` are `NULL`, indicating no child subtrees). When removing a leaf, you can simply delete the `node` and set the parent pointer in the tree to this node to `NULL`. When the node only has 1 subtree, either the `left` or the `right`, you can also still do something relatively simple to assign the orphaned subtree back to the parent, then delete the node with the item that is to be removed. But when the node to be deleted also has both `left` and `right` child subtrees, then you need to do some rearrangements of the tree. The Shaffer textbook discusses how to implement removal from a binary tree as an example you can follow. ## Program Style Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week. 1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation. 1. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers. 1. You should have a document header for your class. The class header document should give a description of the class. Also you should document all private member variables that the class manages in the class document header. 1. Do not include any statements (such as `system("pause")` or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the `system("pause")` which is Microsoft Windows specific.