c++ program most of it coded just need to get it working. please keep most of the logic the same

// Program name: Simple Binary Tree // Purpose: Create a simple binary tree using structures // Author: Kristina Gebel // Date last modified: May 7, 2021 #include using namespace std; #include /* Fill out the code based off the attached template. I am giving you the functions to use. You may choose a different approach, but I would recommend at least using the provided code as a starting point. Test your program with the given driver. You are to insert nodes, display the tree a few times, find some nodes, delete some nodes, display the tree, insert some nodes again, and finally display the tree again. I highly recommend not doing everything thing at once! Comment out some of the code and test things out as you code.

It is okay to pull command out entirely, just be sure your final product has the full driver working.

When you turn in your code, also answer the following:

1. What is the purpose of the function findParentNode? Why is the findNode not sufficient for this assignment?

2. Draw out (by hand or using ASCII art) the final version of the binary tree. This is after all insertions and deletions and insertions and such. (Hint: this is a very good thing to have handy while you are writing the program).

*/ struct TreeNode { int value; //or something else!

TreeNode *left; TreeNode *right; }; // Generally, pass by reference the pointers to the nodes!

int nodeValue(TreeNode *nodePtr); void displayInOrder(TreeNode *nodePtr); void displayPreOrder(TreeNode *nodePtr); void displayPostOrder(TreeNode *nodePtr); void insert(TreeNode *&nodePtr, TreeNode *&newNode); void insertNode(TreeNode *&rootNode, int value); TreeNode* findNode(TreeNode *&rootNode, int value); TreeNode* findParentNode(TreeNode *&rootNode, int value); void deleteNode(TreeNode *&rootNode, int value); int main() { // Display a program heading cout << "Binary Tree!" << endl << endl; int value; int tmpValue = 42; string result; TreeNode* newNode = NULL; newNode = new TreeNode; TreeNode *left; TreeNode *right; TreeNode *tmpNode; TreeNode *rootNode = new TreeNode; TreeNode *tempNodePtr; TreeNode *TempNodePtr2; // Initialize the contents of the node:

rootNode->value = tmpValue; // Set the pointers to NULL:

rootNode->left = NULL; rootNode->right = NULL; newNode->left = NULL; newNode->right = NULL; // Now add some nodes...

insert(rootNode,newNode); insertNode(rootNode, 21); insertNode(rootNode, 38); insertNode(rootNode, 21); insertNode(rootNode, 64); insertNode(rootNode, 20); insertNode(rootNode, 50); insertNode(rootNode, 21); insertNode(rootNode, 55); insertNode(rootNode, 63); insertNode(rootNode, 42); insertNode(rootNode, 28); insertNode(rootNode, 54); insertNode(rootNode, 10); insertNode(rootNode, 12); insertNode(rootNode, 97); cout << endl; // Let's do some displays!

cout << "Displaying nodes in order: " << endl; displayInOrder(rootNode); cout << endl << endl; cout << "Displaying nodes in PRE order: " << endl; displayPreOrder(rootNode); cout << endl << endl; cout << "Displaying nodes in POST order: " << endl; displayPostOrder(rootNode); cout << endl << endl; // Check to make sure the find function works...

tmpValue = 22; tmpNode = findNode(rootNode, tmpValue); result = (tmpNode != NULL) ? " WAS " : " NOT "; cout << "Node " << tmpValue << result << "found!" << endl; tmpValue = 20; tmpNode = findNode(rootNode, tmpValue); result = (tmpNode != NULL) ? " WAS " : " NOT "; cout << "Node " << tmpValue << result << "found!" << endl; cout << endl; // Now for the deletion nodes... Make sure all variations work!

tmpValue = 52; cout << "Attempting to delete node " << tmpValue << endl; deleteNode(rootNode, tmpValue); cout << endl; tmpValue = 50; cout << "Attempting to delete node " << tmpValue << endl; deleteNode(rootNode, tmpValue); cout << endl; tmpValue = 97; cout << "Attempting to delete node " << tmpValue << endl; deleteNode(rootNode, tmpValue); cout << endl; tmpValue = 21; cout << "Attempting to delete node " << tmpValue << endl; deleteNode(rootNode, tmpValue); cout << endl; cout << "Displaying nodes in order: " << endl; displayInOrder(rootNode); cout << endl << endl; // Add some nodes back, just for giggles...

insertNode(rootNode, 52); insertNode(rootNode, 21); insertNode(rootNode, 97); cout << endl; cout << "Displaying nodes in order: " << endl; displayInOrder(rootNode); cout << endl << endl; // Thank the user (it is always good to be polite!) cout << "Thank you!" << endl; return 0; } ///////////////////////////////////////////////////////////////// // Display the value (whatever type it might be!!) of the node...

int nodeValue(TreeNode *nodePtr) { return nodePtr->value; } /////////////////////////////////////////////////////////// // Display the values in the subtree pointed to by nodePtr, // via inorder traversal.

void displayInOrder(TreeNode *nodePtr) { if (nodePtr)//!=NULL { displayInOrder(nodePtr->left); cout << nodeValue(nodePtr) << endl; displayInOrder(nodePtr->right); } } /////////////////////////////////////////////////////////// // Display the values in the subtree pointed to by nodePtr, // via preorder traversal.

void displayPreOrder(TreeNode *nodePtr) { if (nodePtr)//!=NULL { cout << nodeValue(nodePtr) << endl; displayPreOrder(nodePtr->left); displayPreOrder(nodePtr->right); } } /////////////////////////////////////////////////////////// // Display the values in the subtree pointed to by nodePtr, // via postorder traversal.

void displayPostOrder(TreeNode *nodePtr) { if (nodePtr)//!=NULL { displayPostOrder(nodePtr->left); displayPostOrder(nodePtr->right); cout << nodeValue(nodePtr) << endl; } } ///////////////////////////////////////////////////////////// // 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.

void insert(TreeNode *&currentNode, TreeNode *&newNode) { if (currentNode == NULL) { currentNode == newNode; cout << " Inserted node value of " << nodeValue(newNode); } else if (nodeValue(newNode) == nodeValue(currentNode)) { cout << "Duplicate value found for" << nodeValue(newNode) << "Node Not Inserted" << endl; delete newNode; } else if (nodeValue(newNode) < nodeValue(currentNode)) { insert(currentNode->left) } else (nodeValue(newNode) > nodeValue(currentNode)) { insert(currentNode->right, newNode) } } ////////////////////////////////////////////////////////// // insertNode creates a new node to hold num as its value, // and passes it to the insert function.

void insertNode(TreeNode *&rootNode, int value) { ///////////////////// // FILL THIS IN!!! // ///////////////////// } /////////////////////////////////////////////// // findNode determines if a value is present in // the tree. If so, the function returns the node.

// Otherwise, it returns NULL.

TreeNode* findNode(TreeNode *&rootNode, int value) { TreeNode* nodePtr = rootNode; while (nodePtr)//!=NULL (this is what it implys) if (nodeValue(nodePtr) = < value) { return nodeValue; } else if (value = nodeValue(nodePtr)) { nodePtr = nodePtr->left } else { nodePtr = nodePtr->right } return NULL; } ///////////////////////////////////////////////////// // findParentNode determines if a value is present in // the tree. If so, the function returns the parent of the node.

// Otherwise, it returns NULL.

TreeNode* findParentNode(TreeNode *&rootNode, int value) { ///////////////////// // FILL THIS IN!!! // ///////////////////// return NULL; } /////////////////////////////////////////////////////////////// // deleteNode finds the node in the tree that is to be deleted.

// The node is removed and the branches of the tree below // the node are reattached.

// When the node has two children, be careful! Move up the node // from the right side, and then the bottom leftmost node to // repace the deleted node. This is the tricky part!!!

void deleteNode(TreeNode*& rootNode, int value) { TreeNode* nodePtr; TreeNode* nodePtr = findParentNode(rootNode, value); bool isOnLeft = (nodeValue(parentPtr->left->) == value); } nodePtr = (isOnLeft ? parentPtr->left : parentPtr->right); //begin delete of node functions here:

if (parentPtr == NULL) { cout << "Unable to find node for deletion" endl; } //delete nodes with no children else if (nodePtr->left == nodePtr->right) { cout << "Deleting node" << nodePtr << " with no children." endl; isOnLeft ? (parentpointer->left : parentpointer->right) = NULL; delete nodePtr; nodePtr = NULL; } //delete node with left side only else if (nodePtrleft != NULL && nodePtrright == NULL) { cout << "Deleting node" << nodePTr << "child left side only" << endl; isOnLeft ? parentPtrleft->!parentptrright->) = nodePtr->left; delete nodePtr; nodePtr = NULL; } //delete node with right side eonly else if (nodePtrright != NULL && nodePtrleft == NULL) { cout << "Deleting node" << nodePTr << "child right side only" << endl; isOnLeft ? parentPtrleft->!parentptrright->) = nodePtr->right; delete nodePtr; nodePtr = NULL; } //delete node with two children else { cout << "Deleting node" << nodePTr << "children on both sides" << endl; tempNodePtr = nodePtr->right while (tempNode->left !=NULL) { if(tenmpNodePtr-> == NULL) tempNodePtr = tempNodePtr->left } // pp to left and right (isOnLeft ? [arentPtr->left:parentPtr->right])=tempNodePtr; //take sub tree and reattach to right subtreea taking left side and putting it on bottom if (nodePtr->left != tempNodePtr) { tempNodePtr->left = nodePtr->left; } // problem!!

} }