Files Provided:

Sorry, couldn't fit this file on the question so I had to screenshot this file that must be included as well.

bintreetemplate.h

#include #include #include #include

using namespace std; template BinaryTreeNode* create_node( const Item& entry, BinaryTreeNode* l_ptr, BinaryTreeNode* r_ptr ) { BinaryTreeNode* result_ptr;

result_ptr = new BinaryTreeNode; result_ptr->data = entry; result_ptr->left = l_ptr; result_ptr->right = r_ptr;

return result_ptr; }

template BinaryTreeNode* tree_copy(const BinaryTreeNode* root_ptr) { BinaryTreeNode *l_ptr; BinaryTreeNode *r_ptr;

if (root_ptr == NULL) return NULL; else { l_ptr = tree_copy(root_ptr->left); r_ptr = tree_copy(root_ptr->right); return create_node(root_ptr->data, l_ptr, r_ptr); } }

template void tree_clear(BinaryTreeNode*& root_ptr) { if (root_ptr != NULL) { tree_clear(root_ptr->left); tree_clear(root_ptr->right); delete root_ptr; root_ptr = NULL; } }

template bool is_leaf(const BinaryTreeNode& node) { return (node.left == NULL) && (node.right == NULL); }

template void inorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { inorder(f, node_ptr->left); f(node_ptr->data); inorder(f, node_ptr->right); } }

template void postorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { postorder(f, node_ptr->left); postorder(f, node_ptr->right); f(node_ptr->data); } }

template void preorder(Process f, BinaryTreeNode* node_ptr) { if (node_ptr != NULL) { f(node_ptr->data); preorder(f, node_ptr->left); preorder(f, node_ptr->right); } }

template size_t tree_size(const BinaryTreeNode* node_ptr) { if (node_ptr == NULL) return 0; else return 1 + tree_size(node_ptr->left) + tree_size(node_ptr->right); } //template // void printTreeAtDepth (BinaryTreeNode* node_ptr, SizeType depth) // Precondition: node_ptr is a pointer to a node in a binary tree (or node_ptr may be NULL to indicate the empty tree) // If the pointer is NULL, then depth is expected to be 0 // If the pointer !=NULL, then depth is the depth of the node pointed to by node_ptr. // Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr and all its descendants have been written // to cout with the right, depth+1); cout data left, depth+1); } }

template void printTree(BinaryTreeNode* node_ptr) { printTreeAtDepth (node_ptr, 0); }

P4driver.cpp

#include "bintree.h" #include using namespace std;

void eat_white (istream & in) { while ((in.peek()!=EOF) && isspace(in.peek())) in.ignore(); };

void print (int x) {cout

int main () { char command; int value; BinaryTreeNode * tree = NULL; BinaryTreeNode * temp; void printmenu ();

printmenu(); do { eat_white (cin); cin >> command; switch (command) { case '?': printmenu(); break; case 'I': case 'i': cin >> value; cout > value; cout > next; if (next == 'R' || next == 'r') { cout

void printmenu () { cout

SampleData1.txt

Using C++, complete the driver, insert and height functions, both the reflect and delete/remove functions BACKGROUND: You may start with the bintree library and a driver, given to you. Then, you need to write additional (mostly recursive) functions, some either given or described (via an algorithm) in the zyBook/M&Sotes on Canvas, and others on your own (still based on mostly familiar ideas about binary trees). The driver program starts with an empty binary search tree (BST) that can store integer data, and has a loop that would read commands such as the following and calls functions/methods to take the indicated action: I data D data R H S P Insert the specified data value into the BST Delete (remove) the item with the specified data value from the BST (Note that the supporting function will be called remove, since delete is built-in) Clear the tree, making sure to avoid a memory leak Reflect, i.e., create a complete mirror image of the tree (You can either do this in place or create its mirror image, clear the old tree, and make the mirror image the new tree) Print the Height of the tree Print the Size of (i.e., the number of nodes in the tree Print the entire tree sideways in a simple/rudimentary way (for a sanity check, not for perfect pretty output) Traverse in pReorder and print values Traverse in Inorder and print values Traverse in postorder and print values Quit (i.e., end the program, after taking care of all memory leaks) TR TI TO Q Binary Search Trees: Basic Operations & Traversals (including Insert and Delete/Remove) As mentioned above, you can start with the files bintree.h, bintreetemplate.h, and P4driver.cpp. They include much of the basic functionality, including the printTree function to print a specified tree sideways "for sanity check. (You may use the printTree function in your code anytime you have built a partial tree, as long as it has no dangling pointers, so you can check if your tree looks as you expect.) They specifically do not include functions for the height of the tree, or to insert data into a BST, delete/remove data from a BST, or reflect, i.e., create a mirror image, of a binary tree. Binary Search Trees: Reflecting the Tree For the final check, you would complete all the functionality, which includes the driver and insert and height functions (REQUIRED for the midway check), plus both the reflect and delete/remove functions. Hint: The reflect function will be recursive! It is quite short, though! If you are stuck, think about the following (part ii below may be hard to understand; read, reread, and think about it to understand what it says): (i) What is the base case, that is, the simplest case, of a binary tree that needs to be handled? What needs to be done to reflect such a tree? (This may turn out to be very trivial, but that's the beauty of recursion!) (ii) Recall the recursive definition of binary trees from the class: A binary tree is either the null pointer or a pointer to a node that contains some data and two (left and right) pointers to binary (sub)trees. (Note that the italicized part is where the definition becomes recursive.) How can you make use of the recursive portion of this definition in defining the reflect function? Your recursive calls (NOTE THE PLURAL HERE) take care of the recursive portion of the binary tree; what more is needed to get the correct overall result? Make sure to run the program on multiple sets of data, so that you can be sure it works correctly. An input file would include several (I)nsert commands, periodic (H)eight, (S)ize, and (P)rint commands and (T)raversal commands (TR, TI, TO), for the Midway Check, and for the Final Check, a few strategically placed (Delete/remove commands, and (R)eflect commands, followed eventually by a (Quit command. If you want to try it on different trees, before (Quitting, you can (C)lear the tree, and start a new series of commands. The goal would be to insert several data items, test its (H)eight and (S)ize, (P)rint the tree at some strategic points, perhaps show its pre-, post- and in order traversals, create the mirror image and then (P)rint it sometimes, and/or show the pre-, post- and in-order traversals for the mirror image; you should also include some (Delete commands along the way, and check the correctness by (P)rinting and/or (T)raversing in one or more ways. Track your progress roughly by checking against the following suggested milestones: // FILE: bintree.h // PROVIDES: An expanded toolkit of nine template functions for manipulating // binary trees. Each node of the tree contains a piece of data and pointers Il to its left and right children as shown here: // // template Item may be any of the C++ built-in types // struct BinaryTreeNode (int, char, etc.), or a class with a default // { constructor, and an assignment operator. // Item data; // BinaryTreeNode *left; // BinaryTreeNode *right; // } // // The left and right pointers may be NULL to indicate no child. Each tree // is accessed through a pointer to its root. A NULL root pointer indicates an // empty tree. // // FUNCTIONS in the binary tree toolkit: // template BinaryTreeNode* create_node const Item& entry, BinaryTreeNode* Lptr = NULL, BinaryTreeNode* r_ptr = NULL Postcondition: The value returned is a pointer to a newly allocated node with its data equal to entry, and its child pointers equal to l_ptr and r_ptr. Note: If there is insufficient dynamic memory, then the new_handler is called. // // template bool is_leaf(const BinaryTreeNode& node) Postcondition: The return value is true if node is a leaf; otherwise the return value is false. // // // // template void tree_clear (BinaryTreeNode*& root_ptr) Precondition: root_ptr is the root pointer of a binary tree (which may be NULL for the empty tree). Postcondition: All nodes at the root or below have been returned to the heap, and root_ptr has been set to NULL. // // // // // // // // // // // // template BinaryTreeNode* tree_copy(BinaryTreeNode* root_ptr) Precondition: root_ptr is the root pointer of a binary tree (which may be NULL for the empty tree). Postcondition: A copy of the binary tree has been made, and the return value is a pointer to the root of this copy. template void preorder (Process f, BinaryTreeNode*) Precondition: node_ptr is a pointer to a node in a binary tree (or node_ptr may be NULL to indicate the empty tree). Postcondition: If node_ptr is non-NULL, then the function f has been applied to the contents of *node_ptr and all of its descendants, using a pre-order traversal. Note: Process is the type of a function f which may be called with a single Item argument. Item may be any type. template // // // void postorder (Process f, BinaryTreeNode*) Same as the preorder function, except with a post-order traversal. // // // // // template void inorder (Process f, BinaryTreeNode*) Same as the preorder function, except with an in-order traversal. // // // // template void print(BinaryTreeNode* node_ptr, SizeType depth) Precondition: node_ptr is a pointer to a node in a binary tree (or node_ptr may be NULL to indicate the empty tree). If the pointer is not NULL, then depth is the depth of the node pointed to by node_ptr. Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr and all its descendants have been written to cout with the size_t tree_size(const BinaryTreeNode* root_ptr) Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The return value is the number of nodes in the tree. template void print Tree (BinaryTreeNode* node_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The complete tree is printed sideways to provide an intuitive visual view. // // // // template void insert (BinaryTreeNode* & root_ptr, Item Target); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Target is expected NOT to be a value already in the tree. Postcondition: The tree rooted at root_ptr is updated to insert a node containing the Target value. If Target is already present, an error message is issued. // // // // // // // template void remove (BinaryTreeNode* & root_ptr, Item Target); Note: delete is predefined, so we use the name "remove" rather than "delete". Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Target is expected to be a value present in the tree. Postcondition: The tree rooted at root_ptr is updated to remove the node containing the Target value. If Target is not present, an error message is issued. // // // // // // // template BinaryTreeNode* reflect (const BinaryTreeNode* root_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: A mirror image of the tree rooted at root_ptr is created with all new nodes (a la a deep copy) and returned. // // // // template int height(const BinaryTreeNode* root_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The height of the tree is returned. // #ifndef BINTREE_H #define BINTREE_H #include // Provides NULL template struct Binary TreeNode { Item data; BinaryTreeNode* left; Binary TreeNode* right; }; template BinaryTreeNode* create_node const Item& entry, Binary TreeNode* 1_ptr Binary TreeNode* r_ptr ); NULL, NULL template BinaryTreeNode void tree_clear(Binary TreeNode*& root_ptr); template bool is_leaf (const BinaryTreeNode& ptr); template void preorder (Process f, BinaryTreeNode*); template void inorder (Process f, BinaryTreeNode*); template void postorder (Process f, Binary TreeNode*); template size_t tree_size(const BinaryTreeNode* root_ptr); template void printTree (BinaryTreeNode* node_ptr); template void insert (Binary TreeNode* & root_ptr, Item Target); template void remove (Binary TreeNode* & root_ptr, Item Target); // delete is predefined, so we use the name "remove" rather than "delete". template Binary TreeNode* reflect (const BinaryTreeNode* root_ptr); template int height(const Binary TreeNode* root_ptr); #include "bintreetemplate.h" #endif I 50 I 30 I 20 I 40 I 25 I 75 I 60 I 85 I 70 I 80 HHHHHHHHHHHHHATU AHHH AHHHOL TR TI TO D 75 Using C++, complete the driver, insert and height functions, both the reflect and delete/remove functions BACKGROUND: You may start with the bintree library and a driver, given to you. Then, you need to write additional (mostly recursive) functions, some either given or described (via an algorithm) in the zyBook/M&Sotes on Canvas, and others on your own (still based on mostly familiar ideas about binary trees). The driver program starts with an empty binary search tree (BST) that can store integer data, and has a loop that would read commands such as the following and calls functions/methods to take the indicated action: I data D data R H S P Insert the specified data value into the BST Delete (remove) the item with the specified data value from the BST (Note that the supporting function will be called remove, since delete is built-in) Clear the tree, making sure to avoid a memory leak Reflect, i.e., create a complete mirror image of the tree (You can either do this in place or create its mirror image, clear the old tree, and make the mirror image the new tree) Print the Height of the tree Print the Size of (i.e., the number of nodes in the tree Print the entire tree sideways in a simple/rudimentary way (for a sanity check, not for perfect pretty output) Traverse in pReorder and print values Traverse in Inorder and print values Traverse in postorder and print values Quit (i.e., end the program, after taking care of all memory leaks) TR TI TO Q Binary Search Trees: Basic Operations & Traversals (including Insert and Delete/Remove) As mentioned above, you can start with the files bintree.h, bintreetemplate.h, and P4driver.cpp. They include much of the basic functionality, including the printTree function to print a specified tree sideways "for sanity check. (You may use the printTree function in your code anytime you have built a partial tree, as long as it has no dangling pointers, so you can check if your tree looks as you expect.) They specifically do not include functions for the height of the tree, or to insert data into a BST, delete/remove data from a BST, or reflect, i.e., create a mirror image, of a binary tree. Binary Search Trees: Reflecting the Tree For the final check, you would complete all the functionality, which includes the driver and insert and height functions (REQUIRED for the midway check), plus both the reflect and delete/remove functions. Hint: The reflect function will be recursive! It is quite short, though! If you are stuck, think about the following (part ii below may be hard to understand; read, reread, and think about it to understand what it says): (i) What is the base case, that is, the simplest case, of a binary tree that needs to be handled? What needs to be done to reflect such a tree? (This may turn out to be very trivial, but that's the beauty of recursion!) (ii) Recall the recursive definition of binary trees from the class: A binary tree is either the null pointer or a pointer to a node that contains some data and two (left and right) pointers to binary (sub)trees. (Note that the italicized part is where the definition becomes recursive.) How can you make use of the recursive portion of this definition in defining the reflect function? Your recursive calls (NOTE THE PLURAL HERE) take care of the recursive portion of the binary tree; what more is needed to get the correct overall result? Make sure to run the program on multiple sets of data, so that you can be sure it works correctly. An input file would include several (I)nsert commands, periodic (H)eight, (S)ize, and (P)rint commands and (T)raversal commands (TR, TI, TO), for the Midway Check, and for the Final Check, a few strategically placed (Delete/remove commands, and (R)eflect commands, followed eventually by a (Quit command. If you want to try it on different trees, before (Quitting, you can (C)lear the tree, and start a new series of commands. The goal would be to insert several data items, test its (H)eight and (S)ize, (P)rint the tree at some strategic points, perhaps show its pre-, post- and in order traversals, create the mirror image and then (P)rint it sometimes, and/or show the pre-, post- and in-order traversals for the mirror image; you should also include some (Delete commands along the way, and check the correctness by (P)rinting and/or (T)raversing in one or more ways. Track your progress roughly by checking against the following suggested milestones: // FILE: bintree.h // PROVIDES: An expanded toolkit of nine template functions for manipulating // binary trees. Each node of the tree contains a piece of data and pointers Il to its left and right children as shown here: // // template Item may be any of the C++ built-in types // struct BinaryTreeNode (int, char, etc.), or a class with a default // { constructor, and an assignment operator. // Item data; // BinaryTreeNode *left; // BinaryTreeNode *right; // } // // The left and right pointers may be NULL to indicate no child. Each tree // is accessed through a pointer to its root. A NULL root pointer indicates an // empty tree. // // FUNCTIONS in the binary tree toolkit: // template BinaryTreeNode* create_node const Item& entry, BinaryTreeNode* Lptr = NULL, BinaryTreeNode* r_ptr = NULL Postcondition: The value returned is a pointer to a newly allocated node with its data equal to entry, and its child pointers equal to l_ptr and r_ptr. Note: If there is insufficient dynamic memory, then the new_handler is called. // // template bool is_leaf(const BinaryTreeNode& node) Postcondition: The return value is true if node is a leaf; otherwise the return value is false. // // // // template void tree_clear (BinaryTreeNode*& root_ptr) Precondition: root_ptr is the root pointer of a binary tree (which may be NULL for the empty tree). Postcondition: All nodes at the root or below have been returned to the heap, and root_ptr has been set to NULL. // // // // // // // // // // // // template BinaryTreeNode* tree_copy(BinaryTreeNode* root_ptr) Precondition: root_ptr is the root pointer of a binary tree (which may be NULL for the empty tree). Postcondition: A copy of the binary tree has been made, and the return value is a pointer to the root of this copy. template void preorder (Process f, BinaryTreeNode*) Precondition: node_ptr is a pointer to a node in a binary tree (or node_ptr may be NULL to indicate the empty tree). Postcondition: If node_ptr is non-NULL, then the function f has been applied to the contents of *node_ptr and all of its descendants, using a pre-order traversal. Note: Process is the type of a function f which may be called with a single Item argument. Item may be any type. template // // // void postorder (Process f, BinaryTreeNode*) Same as the preorder function, except with a post-order traversal. // // // // // template void inorder (Process f, BinaryTreeNode*) Same as the preorder function, except with an in-order traversal. // // // // template void print(BinaryTreeNode* node_ptr, SizeType depth) Precondition: node_ptr is a pointer to a node in a binary tree (or node_ptr may be NULL to indicate the empty tree). If the pointer is not NULL, then depth is the depth of the node pointed to by node_ptr. Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr and all its descendants have been written to cout with the size_t tree_size(const BinaryTreeNode* root_ptr) Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The return value is the number of nodes in the tree. template void print Tree (BinaryTreeNode* node_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The complete tree is printed sideways to provide an intuitive visual view. // // // // template void insert (BinaryTreeNode* & root_ptr, Item Target); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Target is expected NOT to be a value already in the tree. Postcondition: The tree rooted at root_ptr is updated to insert a node containing the Target value. If Target is already present, an error message is issued. // // // // // // // template void remove (BinaryTreeNode* & root_ptr, Item Target); Note: delete is predefined, so we use the name "remove" rather than "delete". Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Target is expected to be a value present in the tree. Postcondition: The tree rooted at root_ptr is updated to remove the node containing the Target value. If Target is not present, an error message is issued. // // // // // // // template BinaryTreeNode* reflect (const BinaryTreeNode* root_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: A mirror image of the tree rooted at root_ptr is created with all new nodes (a la a deep copy) and returned. // // // // template int height(const BinaryTreeNode* root_ptr); Precondition: root_ptr is a pointer to a node in a binary tree (or root_ptr may be NULL to indicate the empty tree). Postcondition: The height of the tree is returned. // #ifndef BINTREE_H #define BINTREE_H #include // Provides NULL template struct Binary TreeNode { Item data; BinaryTreeNode* left; Binary TreeNode* right; }; template BinaryTreeNode* create_node const Item& entry, Binary TreeNode* 1_ptr Binary TreeNode* r_ptr ); NULL, NULL template BinaryTreeNode void tree_clear(Binary TreeNode*& root_ptr); template bool is_leaf (const BinaryTreeNode& ptr); template void preorder (Process f, BinaryTreeNode*); template void inorder (Process f, BinaryTreeNode*); template void postorder (Process f, Binary TreeNode*); template size_t tree_size(const BinaryTreeNode* root_ptr); template void printTree (BinaryTreeNode* node_ptr); template void insert (Binary TreeNode* & root_ptr, Item Target); template void remove (Binary TreeNode* & root_ptr, Item Target); // delete is predefined, so we use the name "remove" rather than "delete". template Binary TreeNode* reflect (const BinaryTreeNode* root_ptr); template int height(const Binary TreeNode* root_ptr); #include "bintreetemplate.h" #endif I 50 I 30 I 20 I 40 I 25 I 75 I 60 I 85 I 70 I 80 HHHHHHHHHHHHHATU AHHH AHHHOL TR TI TO D 75