jeudi 25 octobre 2018

Error in code when searching through the right subtree in my binary search tree

In one of my classes at Uni we are creating Binary search trees and inserting data and looking them up. My code make sense in my head and because of this I cannot find the error anywhere. I have spent ages trying to find the error but cannot find it anywhere. The only thing that might be causing an error is that the precompiled headers didn't work when I started so i removed them from my project. The error only occurrs when i try to use the BST.Lookup and choose a key that is on the right subtree. This is my main cpp file:

// BinarySearchTrees.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include "BST.h"
#include <iostream>
#include <fstream>
#include <string>

void ReadFile(BST &Bst)
{
    int iKey;
    std::string Key;
    std::string Data;
    std::ifstream testFile("Test.txt");
    if (testFile.is_open())
    {
        while (!testFile.eof())
        {
            getline(testFile, Key, ' ');
            getline(testFile, Data);
            iKey = stoi(Key);
            Bst.Insert(iKey, Data);
        }
    }
}

int main()
{
    std::string Option;
    int Choice;
    BST BST;
    //ReadFile(BST);
    BST.Insert(6, "Oscar");
    BST.Insert(20, "Ben");
    BST.Insert(99, "James");
    BST.Insert(1, "Alex");

    while (Option != "exit")
    {
        std::cout << "If you wish to Lookup a Node, Insert value to find. Enter 'exit' to close" << std::endl;
        getline(std::cin, Option);
        if (Option == "exit")
            break;
        else
        {
            Choice = stoi(Option);
            BST.Lookup(Choice);
        }
    }
    return 0;
}

I believe that the readfile code may be incorrect but am unsure. My Binary Search Tree Class:

#include "BST.h"

struct BST::Node {
    Key key;
    Item item;
    Node* leftChild;
    Node* rightChild;
    Node(Key, Item);
};

void BST::Insert(Key inputKey, Item inputItem)
{
    Node* previousNode = nullptr;
    if (root == nullptr)
    {
        root = new Node(inputKey, inputItem);
    }
    else
    {
        InsertRec(inputKey, inputItem, root, previousNode);
    }
}

void BST::InsertRec(Key inputKey, Item inputItem, Node* & Current, Node* & previousNode)
{
    if (Current != nullptr)
    {
        previousNode = Current;
    }

    bool isLeft = false;

    if (!isLeaf(Current))
    {
        if (inputKey > Current->key)
        {
            isLeft = false;
            InsertRec(inputKey, inputItem, Current->rightChild, previousNode);
        }
        else if (inputKey < Current->key)
        {
            isLeft = true;
            InsertRec(inputKey, inputItem, Current->leftChild, previousNode);
        }
        else
        {
            Current->item = inputItem;
        }
    }
    else
    {
        Current = new Node(inputKey, inputItem);
        if (isLeft)
        {
            previousNode->leftChild = Current;
        }
        else
        {
            previousNode->rightChild = Current;
        }

    }
}

BST::Item* BST::Lookup(Key soughtKey)
{
    Item* Item = LookupRec(soughtKey, root);
    std::string Display = /*std::to_string(soughtKey) + ": " + */ *Item;
    std::cout << Display << std::endl;
    return Item;

}

BST::Item* BST::LookupRec(Key soughtKey, Node* currentNode)
{
    if (!isLeaf(currentNode))
    {
        if ((currentNode->key > soughtKey))
        {
            LookupRec(soughtKey, currentNode->leftChild);
        }
        else if ((currentNode->key < soughtKey))
        {
            LookupRec(soughtKey, currentNode->rightChild);
        }
        else
        {
            return &currentNode->item;
        }
    }

    else
    {
        return nullptr;

    }
}

bool BST::isLeaf(Node* n)
{
    if (nullptr == n)
    {
        return true;
    }

    else
    {
        return false;
    }
}

BST::BST()
{
}

BST::Node::Node(Key K, Item I)
{
    key = K;
    item = I;
    leftChild = nullptr;
    rightChild = nullptr;
}

And finally my header file for the binary search tree:

#pragma once
#include "iostream"
#include "string"

class BST
{
    public:
        using Key = int;
        using Item = std::string;
        void Insert(Key, Item);
        Item* Lookup(Key);
        BST();

    private:
        struct Node;
        Node* root = nullptr;
        static bool isLeaf(Node*);
        static Item* LookupRec(Key, Node*);
        static void InsertRec(Key, Item, Node* &, Node* &);


};

Any help would be greatly appreciated. I've been stuck on this for too long and I cannot progress without fixing this first.

The Test.txt file is filled with keys and items that are read and inputted like how I do it manually at the start of my main function, so I dont think the error is the file data.

Thanks in advance

Aucun commentaire:

Enregistrer un commentaire