Cannot print the list from the binary search tree

[Lacy9265]

Write a program that maintains a database containing data, Name and Birthday. You will be able to enter, remove, modify or search this data. Initially, you can assume that the names are unique. Design a class to represent the database and another to represent the people. Use binary search of people as a data member of the database class. After the user enters some names and birthdays. Then types in the number six which is when the list prints of names/birthdays. However the list of names wont print. I have included the Driver.cpp in this post. However my other classes are too long so I have to post those invidual. I have now posted the BinarySearchTree which have the function to print the list. The code was too long so I had to break it up in two parts. However, all the code is one file called BinarySearchTree.h

Here are the options the user is given.
Enter Add a new person to you list.
Modify Change the name or birthday of a person.
Remove Remove a person from your list.
Search Display the information about a given person (unique name).
Query: Run a query that displays the people by asking the user to enter a month.
Print List everyone in the database.

  #include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <memory>
#include <ctime>
#include <vector>
#include "BinarySearchTree.h"

std::vector<std::string> theTreeSorted;

void display(std::string& anItem)
{
    std::cout << anItem << " ";
    theTreeSorted.push_back(anItem);
}


int main() {

    // Declare variables
    int userChoice = 0; // NUmber user choices from menu
    std::string name; // name of person
    std::string birthday; // person's birthday
    std::string month; // month of person's birthday
    
    

    // For file Birthday.txt
    std::ofstream foutput; 
    std::ifstream finput;
    

    do {
        BinarySearchTree<std::string> theTree; //Error occurs here
        // Give user options on what they want to do with the list
        std::cout << "1.Add a new person to list" << std::endl;
        std::cout << "2.Modify a person's birthday" << std::endl;
        std::cout << "3.Remove a person from the list" << std::endl;
        std::cout << "4.Search for a person by name" << std::endl;
        std::cout << "5.Search for a month(query)" << std::endl;
        std::cout << "6.Print the entire list" << std::endl;
        std::cout << "7.Quit" << std::endl;
        std::cout << "Enter your choice: ";
        std::cin >> userChoice;

        switch (userChoice) {

        // If type '1' then ask user to enter name and birthday
        // then added what user types to list
        case 1:
        {
            std::cout << "Enter name" << std::endl;
            std::cin >> name;
            std::cout << "Enter Birthday (Ex: Month, Day): ";
            std::cin >> birthday;
            theTree.add(name);
            theTree.add(birthday);
            
            
            // Open the Birthday.txt file 
            finput.open("Birthdays.txt");
            foutput.open("Birthdays.txt", std::ios::app);

            // If file is open add name and birthday entered to file 
            if (finput.is_open()) {
                foutput <<"Name: " << name << "   "; // add name 
                foutput <<"Birthday: "  << birthday << std::endl; // add birthday 
            }
            // Close file 
            finput.close();
            foutput.close();

            
        }
        break;

        // If user types '2' then ask user for person's name and new birthday
        // Then delete previous birthday and add new birthday
        case 2:
        {
            std::cout << "Enter name of the person you would like to modify" << std::endl;
            std::cin >> name;
            
            std::cout << "Enter the new person's birthday" << std::endl;
            std::cin >> birthday;

            // Open the Birthday.txt file 
            finput.open("Birthdays.txt");
            foutput.open("Birthdays.txt", std::ios::app);

            // If file is open add name and birthday entered to file 
            if (finput.is_open()) {
                foutput << "Name: " << name << "   "; // add name 
                foutput << "Birthday: " << birthday << std::endl; // add birthday  
            }
            // Close file 
            finput.close();
            foutput.close();

        }
        break;

        // If the user selects '3' then remove person from list
        case 3:
        {
            std::cout << "Enter the name of the person you want to remove" << std::endl;
            std::cin >> name;
            theTree.remove(name);

        }
        break;
        // If user type '4' then search for person name user entered
        // then print the birthday of that person
        case 4:
        {
            std::cout << "Enter the name of the person you want to search for" << std::endl;
            std::cin >> name;
            theTree.getEntry(name);
            
        }
        break;

        // If user types '5' then search for who's birthdays are in month entered by user
        case 5:
        {
            std::cout << "Enter the month you want to search for" << std::endl;
            std::cin >> month;
            theTree.getEntry(month);
            
            
        }
        break;

        // If user types '6' then print the entire list
        case 6:
        {
            theTree.inorderTraverse(display);
        }
        break;

        // If user types '7' then exit program
        case 7:
        {
            exit(1);
        }
        break;
        }

       
    }
    // While the user choice is not to quit 
    while (userChoice != '7');
}

[Lacy9265]

The 1st part of the BinarySearchTree

#ifndef BINARY_SEARCH_TREE_
#define BINARY_SEARCH_TREE_

#include <memory>
#include <string>
#include <iostream>
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcep.h"

template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
    std::shared_ptr<BinaryNode<ItemType>> rootPtr;

protected:
    //------------------------------------------------------------
    // Protected Utility Methods Section:
    // Recursive helper methods for the public methods.
    //------------------------------------------------------------
    // Recursively finds where the given node should be placed and
    // inserts it in a leaf at that point.
    auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
        std::shared_ptr<BinaryNode<ItemType>> newNode);

    // Removes the given target value from the tree while maintaining a
    // binary search tree.
    std::shared_ptr<BinaryNode<ItemType>> removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
        const ItemType target,
        bool& success) override;

    // Removes a given node from a tree while maintaining a
    // binary search tree.
    auto removeNode(std::shared_ptr<BinaryNode<ItemType>> nodePtr);

    // Removes the leftmost node in the left subtree of the node
    // pointed to by nodePtr.
    // Sets inorderSuccessor to the value in this node.
    // Returns a pointer to the revised subtree.
    auto removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
        ItemType inorderSuccessor);

    // Returns a pointer to the node containing the given value,
    // or nullptr if not found.
    std::shared_ptr<BinaryNode<ItemType>> findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
        const ItemType& target, bool& isSuccessful) const;

public:
    //------------------------------------------------------------
    // Constructor and Destructor Section.
    //------------------------------------------------------------
    BinarySearchTree();
    BinarySearchTree(const ItemType& rootItem);
    BinarySearchTree(const BinarySearchTree<ItemType>& tree);
    virtual ~BinarySearchTree();

    //------------------------------------------------------------
    // Public Methods Section.
    //------------------------------------------------------------
    bool isEmpty() const override;
    int getHeight() const override;
    int getNumberOfNodes() const override;
    ItemType getRootData() const throw(PrecondViolatedExcep)override;
    void setRootData(const ItemType& newData) const throw(PrecondViolatedExcep);
    bool add(const ItemType& newEntry) override;
    bool remove(const ItemType& anEntry) override;
    void clear() override;
    ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException)override;
    bool contains(const ItemType& anEntry) const override;

  
    void preorderTraverse(void visit(ItemType&)) const override;
    void inorderTraverse(void visit(ItemType&)) const override;
    void postorderTraverse(void visit(ItemType&)) const override;

    //------------------------------------------------------------
    // Overloaded Operator Section.
    //------------------------------------------------------------
    BinarySearchTree<ItemType>& operator=(const BinarySearchTree<ItemType>& rightHandSide);
}; // end BinarySearchTree

[Lacy9265]

The 2nd part of the BinarySearchTree

//------------------------------------------------------------
   // Protected Utility Methods Section:
   // Recursive helper methods for the public methods.
   //------------------------------------------------------------
   // Recursively finds where the given node should be placed and
   // inserts it in a leaf at that point.
template<class ItemType>
auto BinarySearchTree<ItemType>::placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
    std::shared_ptr<BinaryNode<ItemType>> newNode)
{
    if (subTreePtr == nullptr)
        return newNode;
    else
    {
        if (subTreePtr->getItem() > newNode->getItem())
        {
            subTreePtr->setLeftChildPtr(placeNode(subTreePtr->getLeftChildPtr(), newNode));
        }
        else
        {
            subTreePtr->setRightChildPtr(placeNode(subTreePtr->getRightChildPtr(), newNode));
        }  // end if

        return subTreePtr;
    }
}

// Removes the given target value from the tree while maintaining a
// binary search tree.
template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinarySearchTree<ItemType>::removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
    const ItemType target,
    bool& success)
{
    if (subTreePtr == nullptr)
    {
        success = false;
    }
    else if (subTreePtr->getItem() == target)
    {
        subTreePtr = removeNode(subTreePtr);
        success = true;
    }
    else if (subTreePtr->getItem() > target)
    {
        std::shared_ptr<BinaryNode<ItemType>> tempPtr = removeValue(subTreePtr->getLeftChildPtr(), target, success);
        subTreePtr->setLeftChildPtr(tempPtr);
    }
    else
    {
        std::shared_ptr<BinaryNode<ItemType>> tempPtr = removeValue(subTreePtr->getRightChildPtr(), target, success);
        subTreePtr->setRightChildPtr(tempPtr);
    }

    return subTreePtr;
}

template<class ItemType>
bool BinarySearchTree<ItemType>::add(const ItemType& newData)
{
    auto newNodePtr = std::make_shared<BinaryNode<ItemType>>(newData);
    rootPtr = placeNode(rootPtr, newNodePtr);
    return true;
}
// Removes a given node from a tree while maintaining a
// binary search tree.
template<class ItemType>
auto BinarySearchTree<ItemType>::removeNode(std::shared_ptr<BinaryNode<ItemType>> nodePtr)
{
    if (nodePtr->getLeftChildPtr() == nullptr || nodePtr->getRightChildPtr() == nullptr)
    {
        nodePtr = nullptr;
        return nodePtr;
    }
    else if ((nodePtr->getLeftChildPtr() != nullptr) != (nodePtr->getRightChildPtr() != nullptr))
    {
        std::shared_ptr<BinaryNode<ItemType>> nodeToConnectPtr = nullptr;
        if (nodePtr->getLeftChildPtr() != nullptr)
        {
            nodeToConnectPtr = nodePtr->getLeftChildPtr();
        }
        else
        {
            nodeToConnectPtr = nodePtr->getRightChildPtr();
        }
        return nodeToConnectPtr;
    }
    else
    {
        auto tempPtr = removeLeftmostNode(nodePtr->getRightChildPtr(), nodePtr->getItem());
        nodePtr->setRightChildPtr(tempPtr);
        nodePtr->setItem(nodePtr->getItem());
        return nodePtr;
    }
}

// Removes the leftmost node in the left subtree of the node
// pointed to by nodePtr.
// Sets inorderSuccessor to the value in this node.
// Returns a pointer to the revised subtree.
template<class ItemType>
auto BinarySearchTree<ItemType>::removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
    ItemType inorderSuccessor)
{
    if (subTreePtr->getLeftChildPtr() == nullptr)
    {
        inorderSuccessor = subTreePtr->getItem();
        return removeNode(subTreePtr);
    }
    else
    {
        auto tempPtr = removeLeftmostNode(subTreePtr->getLeftChildPtr(), inorderSuccessor);
        subTreePtr->setLeftChildPtr(tempPtr);
        return subTreePtr;
    }
}

// Returns a pointer to the node containing the given value,
// or nullptr if not found.
template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinarySearchTree<ItemType>::findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
    const ItemType& target, bool& isSuccessful) const
{
    if (treePtr == nullptr)
        return nullptr;
    else if (treePtr->getItem() == target)
    {
        isSuccessful = true;
        return treePtr;
    }

    else if (treePtr->getItem() > target)
        return findNode(treePtr->getLeftChildPtr(), target, isSuccessful);
    else
        return findNode(treePtr->getRightChildPtr(), target, isSuccessful);
}


template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree()
{  }  // end default constructor

template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const ItemType& rootItem)
    :rootPtr(std::make_shared<BinaryNode<ItemType>>(rootItem, nullptr, nullptr))
{  }  // end constructor


template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const BinarySearchTree<ItemType>& tree)
{
    rootPtr = this->copyTree(tree.rootPtr);
}  // end copy constructor

template<class ItemType>
BinarySearchTree<ItemType>::~BinarySearchTree()
{
    this->destroyTree(rootPtr);
}  // end destructor

/*	template<class ItemType>
    bool  BinarySearchTree<ItemType>::isEmpty() const
    {

    }*/
template<class ItemType>
int BinarySearchTree<ItemType>::getHeight() const
{
    return this->getHeightHelper(rootPtr);
}


template<class ItemType>
bool BinarySearchTree<ItemType>::isEmpty() const
{
    return rootPtr == nullptr;
}  // end isEmpty


template<class ItemType>
int BinarySearchTree<ItemType>::getNumberOfNodes() const
{
    return this->getNumberOfNodesHelper(rootPtr);
}  // end getNumberOfNodes

template<class ItemType>
void BinarySearchTree<ItemType>::clear()
{
    this->destroyTree(rootPtr);
    this->rootPtr.reset();
}  // end clear

template<class ItemType>
ItemType BinarySearchTree<ItemType>::getRootData() const throw(PrecondViolatedExcep)
{
    if (isEmpty())
        throw PrecondViolatedExcep("getRootData() called with empty tree.");

    return this->rootPtr->getItem();
}  // end getRootData

template<class ItemType>
void BinarySearchTree<ItemType>::setRootData(const ItemType& newData) const throw(PrecondViolatedExcep)
{
    if (isEmpty())
        this->rootPtr = std::make_shared<BinaryNode<ItemType>>(newData, nullptr, nullptr);
    else
        this->rootPtr->setItem(newData);
}  // end setRootData



template<class ItemType>
ItemType BinarySearchTree<ItemType>::getEntry(const ItemType& anEntry) const throw(NotFoundException)
{
    bool isSuccessful = false;
    auto binaryNodePtr = findNode(rootPtr, anEntry, isSuccessful);

    if (isSuccessful)
        return binaryNodePtr->getItem();
    else
        throw NotFoundException("Entry not found in tree!");
}  // end getEntry

template<class ItemType>
bool BinarySearchTree<ItemType>::contains(const ItemType& anEntry) const
{
    bool isSuccessful = false;
    findNode(rootPtr, anEntry, isSuccessful);
    return isSuccessful;
}  // end contains


template<class ItemType>
bool BinarySearchTree<ItemType>::remove(const ItemType& anEntry)
{
    bool isSuccessful = false;
    rootPtr = removeValue(rootPtr, anEntry, isSuccessful);
    return isSuccessful;
}

//////////////////////////////////////////////////////////////
//      Public Traversals Section
//////////////////////////////////////////////////////////////

template<class ItemType>
void BinarySearchTree<ItemType>::preorderTraverse(void visit(ItemType&)) const
{
    this->preorder(visit, rootPtr);
}  // end preorderTraverse

template<class ItemType>
void BinarySearchTree<ItemType>::inorderTraverse(void visit(ItemType&)) const
{
    this->inorder(visit, rootPtr);
}  // end inorderTraverse

template<class ItemType>
void BinarySearchTree<ItemType>::postorderTraverse(void visit(ItemType&)) const
{
    this->postorder(visit, rootPtr);
}  // end postorderTraverse

#endif

[seeplus]

Now is the time to become familiar with the debugger - if you are not already. Use the debugger to trace through the code monitoring variable values etc to see where execution deviates from that expected from the program design. When you find a variation, you're found a problem. Fix that and try again until the program is as expected.