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 ¤tNode->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