ass5-2/BinarySearchTree.cpp ass5-2/BinarySearchTree.cpp // modified from Frank M. Carrano and Timothy M. Henry. // modified by Matthieu Blanchet and Shashank Chennapragada...

hey, I need help with this assignment, I have my friends assignment, I just want you to make changes and add anything that's missing. I am sure it's not a lot of work to do.


ass5-2/BinarySearchTree.cpp ass5-2/BinarySearchTree.cpp //  modified from Frank M. Carrano and Timothy M. Henry. // modified by Matthieu Blanchet and Shashank Chennapragada #include "BinarySearchTree.h" #include  #include  using namespace std; // BinaryNode constructor w/ item // Pre: none // Post: a binaryNode containing anItem is created BinaryNode::BinaryNode(int anItem) : item(anItem) {} //======================  Constructors/Destructors============================= // Default constructor // Pre: none // Post: a Threaded binary search tree (TBST) has been created BinarySearchTree::BinarySearchTree() = default; // Constructor to generate  nodes , generates n nodes from with values of 1 ,2,. // .. n, adds these nodes to the binary tree such that the tree is balanced! // Pre: nodeArr is number of nodes to add // Post: a TBST had been created with n nodes BinarySearchTree::BinarySearchTree(int nodeArr) {     if (nodeArr > 0) {         vector nodes(nodeArr);         for (int i = 0; i < nodearr; i++) {             nodes[i] =" i + 1;"         }=""         addnodes(nodes, 0, nodearr - 1);=""     }="" }=""  recursive helper function for constructor that adds nodes from a vector to=""  the tree=""  pre: the tbst is empty,nodes contains the nodes to add, front is the=""  front of the vector, back is the back of the vector=""  post: the tbst contains the nodes in "nodes"=""> nodes, int front, int back) {     //base case: if back is lower then front, the array is empty     if (back >= front) {         int midpoint = (back + front) / 2;         add(nodes[midpoint]);//add the halfway point         addNodes(nodes, front, midpoint - 1);         addNodes(nodes, midpoint + 1, back);     } } // Copy constructor // Pre: tree is a TBST // Post:  our TBST is a deep copy of "tree" BinarySearchTree::BinarySearchTree(const BinarySearchTree &tree) {     copyTree(tree.rootPtr); } // Recursive helper function for the copy constructor // Pre: nodeTreePtr is the tree we need to copy values from // Post: values from nodeTreePtr are copied to our TBST void BinarySearchTree::copyTree(const BinaryNode* nodeTreePtr) {     if (nodeTreePtr != nullptr) {         int copyData = nodeTreePtr->item;         add(copyData);         if (!nodeTreePtr->threadLeft) {             copyTree(nodeTreePtr->leftChildPtr);         }         if (!nodeTreePtr->threadRight) {             copyTree(nodeTreePtr->rightChildPtr);         }     } } // Destructor // Pre: none // Post: the TBST's heap memory has been deallocated BinarySearchTree:: ~BinarySearchTree() {     destroyTree(rootPtr); } // Recusive helper function for the destructor // Pre: subtreePtr is the subtree we want to delete // Post: subtreePtr and its children have been deleted void BinarySearchTree::destroyTree(BinaryNode* subTreePtr) {     if (subTreePtr != nullptr) {         if (!subTreePtr->threadLeft || !subTreePtr->threadRight) {             if (!subTreePtr->threadLeft) {                 destroyTree(subTreePtr->leftChildPtr);             }             if (!subTreePtr->threadRight) {                 destroyTree(subTreePtr->rightChildPtr);             }             delete subTreePtr;         } else if (subTreePtr->threadLeft && subTreePtr->threadRight) {             delete subTreePtr;         }     } } //====================== end of Constructors/destructors===================== // Adds a node to the tree, also updates the threads in the tree as necessary // Pre: newData is the int to insert in our tree // Post: our tree contains the node bool BinarySearchTree::add(const int& newData) {     BinaryNode* newPtr = new BinaryNode(newData);     return placeNode(rootPtr, newPtr); } // Recursive helper function for add,  determines where to place a node // Pre: subTreePtr is the tree to add the node, newNodePtr is the node to add // Post: newNodePtr has been added to subTreePtr bool BinarySearchTree::placeNode(BinaryNode *subTreePtr,                                  BinaryNode *newNodePtr) {     if (subTreePtr == nullptr){             // if there's no root         rootPtr = newNodePtr;               // set the root         rootPtr->threadLeft = true;         rootPtr->threadRight = true;         return true;     } else if(subTreePtr->item > newNodePtr->item) {         if(subTreePtr->threadLeft) { // base case there's a right thread!             // set the new node to have the thread             newNodePtr->threadLeft = true;             newNodePtr->leftChildPtr = subTreePtr->leftChildPtr;             newNodePtr->threadRight = true;             newNodePtr->rightChildPtr = subTreePtr;             subTreePtr->threadLeft = false;             subTreePtr->leftChildPtr = newNodePtr;             return true;         }         return placeNode(subTreePtr->leftChildPtr, newNodePtr); //not at the end     } else {                               // subtree <= newnode         // base case there's a right thread!=""         if (subtreeptr-="">threadRight) {             // set the new node to have the thread             newNodePtr->threadRight = true;             newNodePtr->rightChildPtr = subTreePtr->rightChildPtr;             newNodePtr->threadLeft = true;             newNodePtr->leftChildPtr = subTreePtr;             subTreePtr->threadRight = false;             subTreePtr->rightChildPtr = newNodePtr;             return true;         }         return placeNode(subTreePtr->rightChildPtr, newNodePtr);     }     return false; } // Removes a value from a threaded binary search tree, // returns true if successful, false otherwise // Pre: target is the int to remove from our TBST // Post: the target has been removed from our TBST bool BinarySearchTree::remove( const int& target) {     bool successful = false;     removeValue(rootPtr, target, nullptr, successful, false);     return successful; } // Recursive helper method for remove(), recursively locates the node to delete // and calls // Pre: subTreePtr is the tree where we want to remove target, parent is the // parent of subTreePtr, success indicates if we have removed the node correctly // isLeft indicates if the parent is to the left of the child (true if so, // false otherwise) // Post: target has been removed from subTreePtr BinaryNode*  BinarySearchTree::removeValue(BinaryNode* subTreePtr, int target,                                            BinaryNode* parent, bool& success,                                            bool isleft) {     BinaryNode* tempPtr = nullptr; // probably not necessary leave till testing     if (subTreePtr == nullptr) {        //check if rootptr is initialized         return nullptr;     } else if (subTreePtr->item == target) {        // found the target         subTreePtr = removeNode(subTreePtr, isleft, parent);  // Remove the item         success = true;         return subTreePtr;     } else if (subTreePtr->threadRight && subTreePtr->threadLeft) {         //hit a leaf without finding the target         return subTreePtr;     } else if (subTreePtr->item > target) {         // Search the left subtree         tempPtr = removeValue(subTreePtr->leftChildPtr, target, subTreePtr,                               success, false);         subTreePtr->leftChildPtr = tempPtr;         return subTreePtr;     } else {         // Search the right subtree         tempPtr = removeValue(subTreePtr->rightChildPtr, target, subTreePtr,                               success , true);         subTreePtr->rightChildPtr = tempPtr;         return subTreePtr;     } } // Recursive helper for removeValue() // Pre: RemNode is the node to be deleted, isLeft is the location of the parent // left of remNode if true, right otherwise, parent is the parent of remNode // Post: remNode has been deleted and surrounding threads have been updated BinaryNode* BinarySearchTree::removeNode(BinaryNode* remNode, bool isLeft,                                           BinaryNode* parent) {     BinaryNode* tempPtr;     BinaryNode* tempPtr2;   // for rethreading     if ((remNode->threadLeft) && (remNode->threadRight)) {    // is N a leaf?         if (isLeft) {             tempPtr = remNode->rightChildPtr;             // pass back the right pointer status         } else {             tempPtr = remNode->leftChildPtr;             // pass back the left pointer status         }         if (parent != nullptr) {// if there's a parent, it needs to inherit             // the child's threadedness             if (isLeft) {                 parent->threadRight = remNode->threadRight;             } else {                 parent->threadLeft = remNode->threadLeft;             }         }         delete remNode;         remNode = nullptr;         return tempPtr;     } else if ((remNode->threadRight) || (remNode->threadLeft)) {         // N has 1 child         // C replaces N as the child of N's parent         // is the child in the left branch?         if (remNode->threadRight) {             tempPtr = remNode->leftChildPtr;             tempPtr2 = tempPtr;             while (tempPtr2->rightChildPtr != remNode) {                 // runs till tempPtr2 points w/ thread to the Node to be deleted                 tempPtr2 = tempPtr2->rightChildPtr;             }             tempPtr2->rightChildPtr = remNode->rightChildPtr;         } else {        // child is in the right branch             tempPtr = remNode->rightChildPtr;             tempPtr2 = tempPtr;             while (tempPtr2->leftChildPtr != remNode) {                 // runs till tempPtr2 points w/ thread to the Node to be deleted                 tempPtr2 = tempPtr2->leftChildPtr;             }             tempPtr2->leftChildPtr = remNode->leftChildPtr;         }         delete remNode;         remNode = nullptr;         return tempPtr;         // needed to reconnect  child nodes     } else {         // N has two children!         // we need to delete the leftmost node of the right node of N         // and insert that node's value into N         int val;         bool rightThread;         bool isLeft = true;         tempPtr = removeLeftMostNode(remNode->rightChildPtr,                                      val, isLeft, rightThread);         remNode->rightChildPtr = tempPtr;         if (isLeft) {        //should we inherit the right threadedness             remNode->threadRight = rightThread;         }         remNode->item = val;         return remNode;     } } // Recursive helper for removeNode() // Removes the leftmost node in the left subtree of the node pointed to by // remNode. Sets inorderSuccessor to the value in this node. // Pre: RemNode is the node to be deleted, successor is the value of remNode // once we delete it, isLeft indicates if the parent is left or remNode // rightThread stores the threadedness of remNode once we delete it // Post: remNode has been deleted and surrounding threads have been updated // we use successor and rightThread in removeNode to update the previous node to // be deleted BinaryNode* BinarySearchTree::removeLeftMostNode(BinaryNode* remNode,                                                  int& successor, bool& isLeft,                                                  bool& rightThread) {     BinaryNode* tempPtr;     if (remNode->threadLeft) {         // this is the leftmost node , grab its item and delete it.         successor = remNode->item;         rightThread = remNode->threadRight;         return removeNode(remNode, isLeft, nullptr);     } else {         isLeft = false;         remNode->threadLeft = remNode->leftChildPtr->threadLeft;         tempPtr = removeLeftMostNode(remNode->leftChildPtr, successor,                                      isLeft, rightThread);         remNode->leftChildPtr = tempPtr;         return remNode;     } } // Deletes a tree // Pre: A TBST exists // Post: The TBST has been deleted void BinarySearchTree::clear() {     destroyTree(rootPtr); } // Prints out the values of a TBST inorder. // Pre: A TBST exists // Post: The values of the TBST have been printed inorder void BinarySearchTree::inorderTraverse() const {     BinaryNode* curptr = rootPtr;     while (curptr->leftChildPtr != nullptr) {    // go all the way left to start         curptr = curptr->leftChildPtr;     }     cout < curptr->item < " ";     while (curptr-="">rightChildPtr != nullptr) {         if (curptr->threadRight) {      // are we moving using a thread?             // just move forward             curptr = curptr->rightChildPtr;         } else {// if not using thread then we have moved into a subtree             curptr = curptr->rightChildPtr;             // moved into a subtree, need to check left nodes!             while (!curptr->threadLeft) {       // go all the way left                 curptr = curptr->leftChildPtr;             }         }         cout < curptr->item < " ";          print=""     }="">< endl; }="" __macosx/ass5-2/._binarysearchtree.cpp="" __macosx/ass5-2/._cmake-build-debug="" ass5-2/destroytree.cpp="" ass5-2/destroytree.cpp=""   created by frank m. carrano and timothy m. henry.=""   copyright (c) 2017 pearson education, hoboken, new jersey.=""> void BinaryNodeTree::      destroyTree(std::shared_ptr<>> subTreePtr) {    if (subTreePtr != nullptr)    {       destroyTree(subTreePtr–>getLeftChildPtr());       destroyTree(subTreePtr–>getRightChildPtr());       subTreePtr.reset(); // Decrement reference count to node    }  // end if }  // end destroyTree __MACOSX/ass5-2/._destroyTree.cpp ass5-2/getHeightHelper.cpp ass5-2/getHeightHelper.cpp //  Created by Frank M. Carrano and Timothy M. Henry. //  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. template int BinaryNodeTree::     getHeightHelper(std::shared_ptr<>> subTreePtr) const {    if (subTreePtr == nullptr)       return 0;    else       return 1 + max(getHeightHelper(subTreePtr–>getLeftChildPtr()),                      getHeightHelper(subTreePtr–>getRightChildPtr())); }  // end getHeightHelper __MACOSX/ass5-2/._getHeightHelper.cpp ass5-2/CMakeLists.txt cmake_minimum_required(VERSION 3.17) project(ass5) set(CMAKE_CXX_STANDARD 14) add_executable(ass5 main.cpp BinarySearchTree.cpp BinarySearchTree.h BinaryNode.h) __MACOSX/ass5-2/._CMakeLists.txt ass5-2/simplecompile.sh #!/bin/bash # To more easily compile and run this program on CSS Linux Lab # Lines starting with '$' indicate what is typed on command line # if you get the following error: # -bash: ./simplecompile.sh: /bin/bash^M: bad interpreter: No such file or directory # run dos2unix to fix it # $ dos2unix simplecompile.sh # make this file executable # $ chmod 700 simplecompile.sh # redirect the output and stderr from this file to output.txt # $ ./simplecompile.sh > output.txt 2>&1 #TO ENABLE CLANGTIDY do this EVERYTIME on linux lab: scl enable llvm-toolset-7.0 bash date echo "*** compiling with clang++ to create an executable called myprogram" clang++ --version clang++ -std=c++11 -Wall -Wextra -Wno-sign-compare *.cpp -g -o myprogram # echo "*** running clang-tidy using options from .clang-tidy" clang-tidy --version clang-tidy *.cpp -- -std=c++11 echo "*** running myprogram" ./myprogram # valgrind will detect memory leaks echo "*** running with valgrind" valgrind --leak-check=full ./myprogram echo "*** cleaning up, deleting myprogram" rm myprogram date __MACOSX/ass5-2/._simplecompile.sh ass5-2/constructors.cpp ass5-2/constructors.cpp //  Created by Frank M. Carrano and Timothy M. Henry. //  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. template BinaryNodeTree::BinaryNodeTree() : rootPtr(nullptr) { }  // end default constructor template BinaryNodeTree:: BinaryNodeTree(const ItemType& rootItem)       : rootPtr(std::make_shared<>>(rootItem, nullptr, nullptr)) { } // end constructor template BinaryNodeTree:: BinaryNodeTree(const ItemType& rootItem,                const std::shared_ptr<>> leftTreePtr,                const std::shared_ptr<>> rightTreePtr)       : rootPtr(std::make_shared<>>(rootItem,                                                        copyTree(leftTreePtr–>rootPtr),                                                        copyTree(rightTreePtr–>rootPtr)) { } // end constructor template BinaryNodeTree:: BinaryNodeTree(const BinaryNodeTree& treePtr) {    rootPtr = copyTree(treePtr.rootPtr); }  // end copy constructor template std::shared_ptr<>> BinaryNodeTree::copyTree(      const std::shared_ptr<>> oldTreeRootPtr) const {    std::shared_ptr<>> newTreePtr;        // Copy tree nodes during a preorder traversal    if (oldTreeRootPtr != nullptr)    {       // Copy node       newTreePtr = std::make_shared<>>(oldTreeRootPtr–>getItem(),                                                           nullptr, nullptr);       newTreePtr–>setLeftChildPtr(copyTree(oldTreeRootPtr–>getLeftChildPtr()));       newTreePtr–>setRightChildPtr(copyTree(oldTreeRootPtr–>getRightChildPtr()));    }  // end if    // Else tree is empty (newTreePtr is nullptr)        return newTreePtr; }  // end copyTree __MACOSX/ass5-2/._constructors.cpp ass5-2/create-output.sh #!/bin/bash # Run this script as `./create-output.sh > output.txt 2>&1` # How we want to call our executable, # possibly with some command line parameters EXEC_PROGRAM="./a.out " # Timestamp for starting this script date MACHINE="" # Display machine name if uname command is available if hash uname 2>/dev/null; then uname -a MACHINE=`uname -a` fi # Display user name if id command is available if hash id 2>/dev/null; then id fi # If we are running as a GitHub action, install programs GITHUB_MACHINE='Linux fv-az' if [[ $MACHINE == *"${GITHUB_MACHINE}"* ]]; then echo "=====================================================" echo "Running as a GitHub action, attempting to install programs" echo "=====================================================" sudo apt-get install llvm clang-tidy clang-format valgrind fi # If we are running on CSSLAB and # clang-tidy is not active, print a message CSSLAB_MACHINE='Linux csslab' CLANG_TIDY_EXE='/opt/rh/llvm-toolset-7.0/root/bin/clang-tidy' if [[ $MACHINE == *"${CSSLAB_MACHINE}"* ]]; then if ! hash clang-tidy 2>/dev/null && [ -e "${CLANG_TIDY_EXE}" ] ; then echo "=====================================================" echo "ERROR ERROR ERROR ERROR ERROR ERROR ERROR ERROR ERROR " echo "clang-tidy NOT found in path (but is in $CLANG_TIDY_EXE )" echo "Add the following command to ~/.bashrc file" echo " source scl_source enable llvm-toolset-7.0" echo "You can add the command by executing the following line" echo " echo \"source scl_source enable llvm-toolset-7.0\" >> ~/.bashrc" echo "=====================================================" fi fi # delete a.out, do not give any errors if it does not exist rm ./a.out 2>/dev/null echo "=====================================================" echo "1. Compiles without warnings with -Wall -Wextra flags" echo "=====================================================" g++ -g -std=c++11 -Wall -Wextra -Wno-sign-compare *.cpp echo "=====================================================" echo "2. Runs and produces correct output" echo "=====================================================" # Execute program $EXEC_PROGRAM echo "=====================================================" echo "3. clang-tidy warnings are fixed" echo "=====================================================" if hash clang-tidy 2>/dev/null; then clang-tidy *.cpp -- -std=c++11 else echo "WARNING: clang-tidy not available." fi echo "=====================================================" echo "4. clang-format does not find any formatting issues" echo "=====================================================" if hash clang-format 2>/dev/null; then # different LLVMs have slightly different configurations which can break things, so regenerate echo "# generated using: clang-format -style=llvm -dump-config > .clang-format" > .clang-format clang-format -style=llvm -dump-config >> .clang-format for f in ./*.cpp; do echo "Running clang-format on $f" clang-format $f | diff $f - done else echo "WARNING: clang-format not available" fi echo "=====================================================" echo "5. No memory leaks using g++" echo "=====================================================" rm ./a.out 2>/dev/null g++ -std=c++11 -fsanitize=address -fno-omit-frame-pointer -g *.cpp # Execute program $EXEC_PROGRAM > /dev/null echo "=====================================================" echo "6. No memory leaks using valgrind, look for \"definitely lost\" " echo "=====================================================" rm ./a.out 2>/dev/null if hash valgrind 2>/dev/null; then g++ -g -std=c++11 *.cpp # redirect program output to /dev/null will running valgrind valgrind --log-file="valgrind-output.txt" $EXEC_PROGRAM > /dev/null cat valgrind-output.txt rm valgrind-output.txt 2>/dev/null else echo "WARNING: valgrind not available" fi echo "=====================================================" echo "7. Tests have full code coverage" echo "=====================================================" ./check-code-coverage.sh # Remove the executable rm ./a.out* 2>/dev/null date echo "=====================================================" echo "To create an output.txt file with all the output from this script" echo "Run the below command" echo " ./create-output.sh > output.txt 2>&1 " echo "=====================================================" __MACOSX/ass5-2/._create-output.sh ass5-2/clang-tidy # Configuration options for clang-tidy # CSS Linux machines, Sep 2019: LLVM version 3.8.1 # # usage: clang-tidy *.cpp -- -std=c++11 # # --- # See https://clang.llvm.org/extra/clang-tidy/#using-clang-tidy for all possible checks Checks: '*,-fuchsia-*,-cppcoreguidelines-owning-memory,-cppcoreguidelines-pro-bounds-array-to-pointer-decay,-cppcoreguidelines-pro-bounds-pointer-arithmetic,-google-build-using-namespace,-hicpp-no-array-decay,-modernize-use-trailing-return-type,-llvm-header-guard,-cert-err60-cpp,-cppcoreguidelines-pro-bounds-constant-array-index,-google-global-names-in-headers' WarningsAsErrors: '*' HeaderFilterRegex: '.*' CheckOptions: - { key: readability-identifier-naming.ClassCase, value: CamelCase } - { key: readability-identifier-naming.StructCase, value: CamelCase } - { key: readability-identifier-naming.EnumCase, value: CamelCase } - { key: readability-identifier-naming.GlobalConstantCase, value: UPPER_CASE } - { key: readability-identifier-naming.VariableCase, value: camelBack } - { key: readability-identifier-naming.ParameterCase, value: camelBack } - { key: readability-identifier-naming.PublicMemberCase, value: camelBack } # No good consensus on function names problem.isFinished() and GetInputFromUser() are both good # - { key: readability-identifier-naming.FunctionCase, value: camelBack } # - { key: readability-identifier-naming.PublicMethodCase, value: camelBack } # - { key: readability-identifier-naming.PrivateMethodCase, value: camelBack } ######################################################################## # Disabled checks ######################################################################## # -fuchsia-*, # Checks associated with fuchsia operating system # -cppcoreguidelines-owning-memory, # Using and learning about raw pointers, not type-based semantics of gsl::owner # -cppcoreguidelines-pro-bounds-array-to-pointer-decay, # Using pointers to arrays # -cppcoreguidelines-pro-bounds-pointer-arithmetic, # Not using

which is in C++20 # -google-build-using-namespace, # Will use "using namespace std" to make code easier to read # -hicpp-no-array-decay, # Using pointers to arrays # -modernize-use-trailing-return-type, # Not using the modern return type indications such as "factorial(int n) -> int" # -llvm-header-guard # Will use short header guards not full directory and file name # -cert-err60-cpp # Want to be able to throw exception with string # -cppcoreguidelines-pro-bounds-constant-array-index # Want to use array[index] without having to use gsl::at() # -google-global-names-in-headers # Readbility, want to have "using namespace std;" in headers as well __MACOSX/ass5-2/._clang-tidy ass5-2/inorder.cpp ass5-2/inorder.cpp //  Created by Frank M. Carrano and Timothy M. Henry. //  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. template void BinaryNodeTree::      inorder(void visit(ItemType&),              std::shared_ptr<>> treePtr) const {    if (treePtr != nullptr)    {       inorder(visit, treePtr–>getLeftChildPtr());       ItemType theItem = treePtr–>getItem();       visit(theItem);       inorder(visit, treePtr–>getRightChildPtr());    }  // end if }  // end inorder __MACOSX/ass5-2/._inorder.cpp ass5-2/BinarySearchTree.h // Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. // modified by Matthieu Blanchet and Shashank Chennapragada #include "BinaryNode.h" #include #ifndef BINARY_SEARCH_TREE_ #define BINARY_SEARCH_TREE_ using namespace std; class BinarySearchTree { private: BinaryNode* rootPtr = nullptr;// pointer to the tree's start //------------------------------------------------------------ // Recursive helper methods //------------------------------------------------------------ // recursive helper function for add, determines where to place a node // Pre: subTreePtr is the tree to add the node, newNodePtr is the node to // add // Post: newNodePtr