To start this assignment, copy the files for this assignment which can be found in:
This folder contains all the files necessary for this assignment. The specification for the Binary_tree class is in the file, binary_tree.h. The implementation is in the file, binary_tree.cc. The file test_tree.cc contains source code for testing the Binary_tree implementation.
To complete this problem you should do the following:
Hints: recursive_size() takes one parameter, sub_root, which is a pointer to the root (or subroot) of the tree (or subtree) for which the number of nodes will be returned. If sub_root is NULL, the tree is empty, so there are no nodes in the tree. If sub_root is pointing to a node, the number of nodes in the tree is 1 (the node being pointed to) plus the number of nodes in the left sub_tree of that node plus the number of nodes in the right sub_tree of that node.
recursive_clear() also takes one parameter, sub_root, which is a pointer to the root (or subroot) of the tree (or subtree) to be cleared. If the pointer is NULL, the tree is empty, so it is already cleared. If the pointer points to a node, the function must first clear the lefthand subtree of that node, then clear the righthand subtree of that node. Finally, it must clear the node pointed to by sub_root. This is accomplished by creating a temporary pointer that points to that node, then assigning sub_root to NULL, and finally deleting the node (by deleting the temporary pointer).
Test your function by compiling and running it with the test_tree.cc code. Use the compile command:
A sample output is as follows:
Creating first test tree. The tree in preorder is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The tree in inorder is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 The tree in postorder is: 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 The size of the tree is 20 After clearing, the size of the tree is 0 Creating second test tree. The tree in preorder is: 5 2 1 3 4 7 6 8 9 10 The tree in inorder is: 1 2 3 4 5 6 7 8 9 10 The tree in postorder is: 1 4 3 2 6 10 9 8 7 5 The size of the tree is 10 After clearing, the size of the tree is 0
When you are done, submit a soft copy of your programs using the submit function. Also copy and paste the 4 functions you wrote for this problem ( size(), recursive_size(), clear() and recursive_clear()), along with your file prologue for binary_tree.cc into a separate file so you can print it out and hand it in.
For each of the following problems, write your answer on the Homework 9 Answer sheet.
1. Determine the order in which the vertices of the following binary tree will be visited under (1) preorder, (2) inorder, and (3) postorder traversal.
2. Draw expression trees for each of the following expressions, and show the order of visiting the vertices in (1) preorder, (2) inorder, and (3) postorder:
(a) log n!
(b) (a - b) - c
Problem 3 is based on the following binary search tree:
3. Insert each of the following keys into the preceding binary search tree. Draw the resulting Tree. Show the comparisons of keys that will be made in each case. Do each part independently, inserting the key into the original tree.
4. Draw the binary search trees that function insert() will construct for the list of 14 names presented in the following order and inserted into a previously empty binary search tree.
Make sure you include a file prologue with your name, class, lecture section, the date, and the assignment number, along with a description of the file contents and their purpose. Also include appropriate comments for each of the functions you implement (with proper pre and post conditions).
Home | | Syllabus | | Assignments | | Lecture Notes