Ошибка в коде при поиске через правильное поддерево в моем бинарном дереве поиска - PullRequest
Новая
       9

Ошибка в коде при поиске через правильное поддерево в моем бинарном дереве поиска

0 голосов
/ 25 октября 2018

В одном из моих классов в Uni мы создаем деревья бинарного поиска, вставляем данные и ищем их.Мой код имеет смысл в моей голове, и из-за этого я нигде не могу найти ошибку.Я потратил целую вечность, пытаясь найти ошибку, но нигде не могу ее найти.Единственное, что может вызывать ошибку, это то, что предварительно скомпилированные заголовки не работали при запуске, поэтому я удалил их из своего проекта.Ошибка возникает только тогда, когда я пытаюсь использовать BST.Lookup и выбрать ключ, который находится на правом поддереве.Это мой основной файл cpp: 

// 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;
}

Я считаю, что код readfile может быть неправильным, но я не уверен.Мой класс бинарного дерева поиска: 

#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;
}

И, наконец, мой заголовочный файл для дерева бинарного поиска: 

#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* &);


};

Любая помощь будет принята с благодарностью.Я застрял на этом слишком долго, и я не могу прогрессировать, не исправив сначала.

Файл Test.txt заполнен ключами и элементами, которые читаются и вводятся, как, как я делаю это вручную в началемоей основной функции, поэтому я не думаю, что ошибка в данных файла.

Заранее спасибо

1 Ответ

0 голосов
/ 25 октября 2018

ОБНОВЛЕНИЕ: наконец-то нашли ошибку.Проблема была с bool isLeft в моей функции InsertRec.Значение bool всегда было ложным из-за рекурсии, поэтому изменили код для сравнения previousNode-> Key с Current-> Key, чтобы определить, идет ли ребенок влево или вправо

...