write a program that inserts the following numbers 20, 5, 8, 3, 12, 9, 2, 16 into the tree in that order.

- Announce the numbers being inserted

- Output the number of nodes, and then display them in order

- Delete 8 and 12 from the tree

- Output the number of nodes, and then display them in order

- Display the tree in postorder

- Modify the header as needed to output the values horizontally

- Display the tree as it exists and replace the Xs with the correct value in the nodes.

- Use cout statements and only display branches that exist

The program will have the header file (BinaryTree.h) and your main program.

NOTE: Older compilers do not accept nullptr, use NULL to initialize pointers.

Use the following Header code.

#ifndef BINARYTREE_H #define BINARYTREE_H #include using namespace std; template class BinaryTree { public: struct TreeNode { T value; TreeNode *left; TreeNode *right; }; TreeNode *root; void insert(TreeNode *&, TreeNode *&); void destroySubTree(TreeNode *); void deleteNode(T, TreeNode *&); void makeDeletion(TreeNode *&); void displayInOrder(TreeNode *); void displayPreOrder(TreeNode *); void displayPostOrder(TreeNode *); int countNodes(TreeNode *&); public: BinaryTree() // Constructor { root = nullptr; } ~BinaryTree() // Destructor { destroySubTree(root); } void insertNode(T); bool searchNode(T); void remove(T); void displayInOrder() { displayInOrder(root); } void displayPreOrder() { displayPreOrder(root); } void displayPostOrder() { displayPostOrder(root); } int numNodes(); };

//************************************************************* // insert accepts a TreeNode pointer and a pointer to a node. The function inserts the * // node into the tree pointed to by the TreeNode pointer. This function is called recursively. * //************************************************************* template void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode) { if (nodePtr == nullptr) { // Insert the node. nodePtr = newNode; } else if (newNode->value value) { // Search the left branch insert(nodePtr->left, newNode); } else { // Search the right branch insert(nodePtr->right, newNode); } } //********************************************************** // insertNode creates a new node to hold num as its value, * // and passes it to the insert function. * //********************************************************** template void BinaryTree::insertNode(T num) { TreeNode *newNode = nullptr; // Pointer to a new node. // Create a new node and store num in it. newNode = new TreeNode; newNode->value = num; newNode->left = newNode->right = nullptr; // Insert the node. insert(root, newNode); } //*************************************************** // destroySubTree is called by the destructor. It * // deletes all nodes in the tree. * //*************************************************** template void BinaryTree::destroySubTree(TreeNode *nodePtr) { if (nodePtr->left) { destroySubTree(nodePtr->left); } if (nodePtr->right) { destroySubTree(nodePtr->right); }

delete nodePtr; }

//*************************************************** // searchNode determines if a value is present in the tree. If so, * // the function returns true. Otherwise, it returns false. * //*************************************************** template bool BinaryTree::searchNode(T num) { bool status = false; TreeNode *nodePtr = root; while (nodePtr) { if (nodePtr->value == num) { status = true; } else if (num value) { nodePtr = nodePtr->left; } else { nodePtr = nodePtr->right; } } return status; } //********************************************** // remove calls deleteNode to delete the * // node whose value member is the same as num. * //********************************************** template void BinaryTree::remove(T num) { deleteNode(num, root); } //******************************************** // deleteNode deletes the node whose value * // member is the same as num. * //******************************************** template void BinaryTree::deleteNode(T num, TreeNode *&nodePtr) { if (num value) { deleteNode(num, nodePtr->left); } else if (num > nodePtr->value) { deleteNode(num, nodePtr->right); } else { makeDeletion(nodePtr); } } //*********************************************************** // makeDeletion takes a reference to a pointer to the node that is to be deleted. * // The node is removed and the branches of the tree below the node are reattached. * //*********************************************************** template

void BinaryTree::makeDeletion(TreeNode *&nodePtr) { // Temporary pointer, used in reattaching the left subtree. TreeNode *tempNodePtr = nullptr; if (nodePtr == nullptr) { cout

else if (nodePtr->right == nullptr) { tempNodePtr = nodePtr; nodePtr = nodePtr->left; // Reattach the left child delete tempNodePtr; } else if (nodePtr->left == nullptr) { tempNodePtr = nodePtr; nodePtr = nodePtr->right; // Reattach the right child delete tempNodePtr; } // If the node has two children. else { // Move one node the right. tempNodePtr = nodePtr->right; // Go to the end left node. while (tempNodePtr->left) { tempNodePtr = tempNodePtr->left; }

// Reattach the left subtree. tempNodePtr->left = nodePtr->left; tempNodePtr = nodePtr; // Reattach the right subtree. nodePtr = nodePtr->right; delete tempNodePtr; } } //**************************************************************** // The displayInOrder member function displays the values * // in the subtree pointed to by nodePtr, via inorder traversal. * //**************************************************************** template void BinaryTree::displayInOrder(TreeNode *nodePtr) { if (nodePtr) { displayInOrder(nodePtr->left); cout value right); } } //**************************************************************** // The displayPreOrder member function displays the values * // in the subtree pointed to by nodePtr, via preorder traversal. * //**************************************************************** template void BinaryTree::displayPreOrder(TreeNode *nodePtr) { if (nodePtr) { cout value left); displayPreOrder(nodePtr->right); } } //**************************************************************** // The displayPostOrder member function displays the values * // in the subtree pointed to by nodePtr, via postorder traversal.* //**************************************************************** template void BinaryTree::displayPostOrder(TreeNode *nodePtr) { if (nodePtr) { displayPostOrder(nodePtr->left); displayPostOrder(nodePtr->right); cout value int BinaryTree::numNodes() { return countNodes(root); } //**************************************************************** // The countNodes function uses recursion to count the nodes in the tree. // This function is called by the public member function numNodes. //**************************************************************** template int BinaryTree::countNodes(TreeNode *&nodePtr) { int count; if (nodePtr == nullptr) { count = 0; } else { count = 1 + countNodes(nodePtr->left) + countNodes(nodePtr->right); } return count; } #endif

Inserting nodes with 20, 5, 8, 3, 12, 9, 2, and 16 The number of nodes in the tree is now 8 Here are the values in the tree in order 2 3 5 8 9 12 16 20 Now deleting 8 from the tree... Now deleting 12 from the tree. . The number of nodes in the tree is now 6 Here are the values in the tree in order: 2 3 5 9 16 20 Here are the values in the tree in POST order 2 3 9 16 5 20 Tree Process returned 0 (0x0 excution time0.016 s Press any key to continue Inserting nodes with 20, 5, 8, 3, 12, 9, 2, and 16 The number of nodes in the tree is now 8 Here are the values in the tree in order 2 3 5 8 9 12 16 20 Now deleting 8 from the tree... Now deleting 12 from the tree. . The number of nodes in the tree is now 6 Here are the values in the tree in order: 2 3 5 9 16 20 Here are the values in the tree in POST order 2 3 9 16 5 20 Tree Process returned 0 (0x0 excution time0.016 s Press any key to continue