0

I need to read values (movies) from a text file and insert them into a binary search tree one by one. In my Store.h class, I have a BST inventory which, which is a binary search tree (BST) object that represents the tree everything is supposed to get stored into.

The problem is that although my insert method in BST.cpp seems to generally work, rather than storing all the values from the file in the tree, only the last value from the last time the file-reading loop runs is stored. I.e. when I print out the BST inventory, it only shows that the last movie in the file is stored. When printing out one by one, it shows that only the movie in that loop is stored, then that information is lost when the next loop goes.

How do I ensure that the values I insert are saved in the BST after every loop?

Note: In my BST.cpp file, the isEmpty() method is incorrect (because size is never updated, so this is irrelevant). However, at one point everything worked as expected with this logic. I tried to fix the isEmpty() method by changing it to

bool BST::isEmpty() {
    return root == nullptr;
}

However, when I compile and run, the entire .exe just stops working. I have been debugging for hours, but I still don't know how to solve the problem. And I have no idea why everything worked at one point, even though I barely changed anything. PLEASE HELP.

Here is a condensed version of the files I'm working with:

Store.h (client code header):

#ifndef STORE_H
#define STORE_H
#include <iostream>
#include <string>
#include <fstream>
#include "BST.h"
#include "MovieFactory.h"
#include "Movie.h"
#include <list>
#include <sstream>
using namespace std;

class Store {

    public:
        Store();
        void buildMovies(ifstream& file);
        void buildCustomers(ifstream& file);
        void processTransactions(ifstream& file);

private:
    BST inventory;

};
#endif

Store.cpp (client code):

#include "Store.h"

void Store::buildMovies(ifstream& file) {
    if (!file) {
        cout << "Error: File not found.";
    }
    string movieData;
    while (!file.eof()) {
        getline(file, movieData);
        Movie* newMovie = movieFactory.createMovie(movieData);
        newMovie->setData(movieData);
        inventory.insert(newMovie);
    }
}

BST.h:

#ifndef BST_H
#define BST_H
#include <iostream>
#include "Movie.h"
using namespace std;

class BST {
    protected:
        struct Node {
                Movie* data;           // pointer to object of data stored
               Node* left;               // pointer to left child Node
                Node* right;              // pointer to right child Node
        };

    public:
        bool insert(Movie* movie);
        bool isEmpty();

    private:
        Node* root;
        int size;
};
#endif

BST.cpp:

#include "BST.h"

bool BST::insert(Movie* movie) {
    Node* ptr = new Node;
    ptr->data = movie;
    movie = nullptr;
    ptr->left = ptr->right = nullptr;
    if (isEmpty()) {
         root = ptr;
    }
    else
    {
        Node *current = root;
        bool inserted = false;

        while (!inserted)
        {
            if (*ptr->data < *current->data)
            {
                if (current->left == nullptr)
                { // at leaf, insert left
                    current->left = ptr;
                    inserted = true;
                }
                else
                    current = current->left; // one step left
            }
            else
            {
                if (current->right == nullptr)
                { // at leaf, insert right
                    current->right = ptr;
                    inserted = true;
                }
                else
                    current = current->right; // one step right
            }
        }
    }
    return true;
}

bool BST::isEmpty() {
    return size == 0;
}
pltmswuiswrpmasktc
  • 1
  • Are you *required* to use your own BST? Because `std::set` or `std::map` actually implement one, too. You might need to provide a custom comparer or a specialisaton of `std::less`, though. As a bonus, these (usually at least) implement a red-black tree, which avoids degenerate trees your algorithm can easily produce (extreme case: sorted input which lets decay your tree to a linked list). – Aconcagua Jun 08 '21 at 16:09
  • Your `BST` does not provide a constructor initialising `root`, which thus remains at an indeterminate value. As you have dynamic memory management involved, you should follow the [rule of three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) or its C++11 optimised variant, the [rule of five](https://stackoverflow.com/questions/4782757/rule-of-three-becomes-rule-of-five-with-c11). – Aconcagua Jun 08 '21 at 16:15
  • While for C, the same applies for C++ as well: https://xspdf.com/help/50639735.html – Aconcagua Jun 08 '21 at 16:17
  • How does your movie factory look like? I suspect it to return one and the same instance again and again... – Aconcagua Jun 08 '21 at 16:18

0 Answers0