Ошибка c ++ LNK2019: двоичное дерево поиска

Думая, что есть проблема с моим корневым объявлением, три ошибки появляются в моей функции вставки, конструкторе по умолчанию и деструкторе.

Если я #include .cpp файл: есть проблема с моей функцией вставки и правильным построением дерева. Я наблюдаю за своими локальными переменными, и root ведет себя странно - после добавления первого значения root указывает на то, что не имеет данных. (Я новичок в C ++, поэтому, пожалуйста, подождите, я впервые создаю шаблонный класс и бинарное дерево поиска)

Он генерирует исключение каждый раз, когда достигает строки while (p-> data! = Item).

Вот моя функция вставки:

    template <class Item>
void Tree<Item>::insert(Item item)
{
    Node<Item> *new_node = new Node<Item>();
    new_node->data = item;

    if (root == nullptr)
    {
        root = new_node;
    }
    else
    {
        Node<Item> *q = nullptr;
        Node<Item> *p = root;
        while (p != nullptr && q->data != item)
        {
            q = p;
            if (item < p->data)
            {
                q = p->lchild;
            }
            else if (item > p->data)
            {
                q = p->rchild;
            }
        }
        if (q->data == item)
        {
            cout << "Duplicate Data" << endl;
        }
        else
        {
            if (item > q->data)
            {
                q->rchild = new_node;
            }
            else
            {
                q->lchild = new_node;
            }
        }
    }
}

Заголовок:

#pragma once
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

template <class Item>
struct Node
{
    //Default constructor for Node
    //Purpose: Initialize all values
    //Parameters: None
    //Returns: None
    Node();

    //Parameterized constructor for Node
    //Purpose: Initialize all values
    //Parameters: a data Item, and Node pointers for left and right children
    //Returns: None
    Node(Item, Node<Item>*, Node<Item>*);

    //variables
    Item data;
    Node<Item> *lchild;
    Node<Item> *rchild;
};

template <class Item>
class Tree
{

public:
    //Default constructor for Tree
    //Purpose: Initialize all values
    //Parameters: None
    //Returns: None
    Tree();

    //Copy constructor
    //Purpose: create new Tree
    //Parameters: A Tree object
    //Returns: Tree
    Tree(const Tree&);

    //copy
    //Purpose: To copy values
    //Parameters: Node pointer
    //Returns: None
    void copy(Node<Item>*);

    //chop
    //Purpose: Delete tree
    //Parameters: Node pointer
    //Returns: None
    void chop(Node<Item>*);

    //Destructor
    //Purpose: Clean up data, delete tree
    //Parameters: None
    //Returns: None
    ~Tree();

    //operator=
    //Purpose: Overload assignment operator
    //Parameters: a const ref to a Tree object
    //Returns: Tree
    const Tree<Item>&operator=(const Tree&);

    //insert
    //Purpose: To add a value to tree
    //Parameters: A const reference to an Item
    //Returns: None
    void insert(Item);

    //inOrderTraverse
    //Purpose: To traverse the tree in order
    //Parameters: A Node pointer
    //Returns: None
    //void inOrderTraverse(Item);


private:
    Node<Item> *root;
};

А вот и мой класс Tree:

   #include "Tree.h"

template <class Item>
Node<Item>::Node()
{
    data = 0;
    lchild = nullptr;
    rchild = nullptr;
}

template <class Item>
Node<Item>::Node(Item _data, Node<Item> *_lchild, Node<Item> *_rchild)
{
    data = _data;
    lchild = _lchild;
    rchild = _rchild;
}

template <class Item>
Tree<Item>::Tree()
{
    root = nullptr;
}

template <class Item>
void Tree<Item>::copy(Node<Item> *c)
{
    if (c)
    {
        insert(c->data);
        copy(c->lchild);
        copy(c->rchild);
    }
}

template <class Item>
void Tree<Item>::chop(Node<Item> *c)
{
    if (c)
    {
        chop(c->lchild);
        chop(c->rchild);
        delete c;
    }
}

template <class Item>
Tree<Item>::Tree(const Tree& t)
{
    root = nullptr;
    copy(t.root);
}

template <class Item>
Tree<Item>::~Tree()
{
    chop(root);
}

template <class Item>
const Tree<Item>&Tree<Item>::operator=(const Tree& t)
{
    if (this != &t)
    {
        chop(root);
        root = nullptr;
        copy(t.root);
    }
    return *this;
}

template <class Item>
void Tree<Item>::insert(Item item)
{
    Node<Item> *new_node = new Node<Item>();
    new_node->data = item;

    if (root == nullptr)
    {
        root = new_node;
    }
    else
    {
        Node<Item> *p = root;
        Node<Item> *q = nullptr;
        while (p->data != item)
        {
            q = p;
            if (item < p->data)
            {
                p = p->lchild;
            }
            else if (item > p->data)
            {
                p = p->rchild;
            }
        }
        if (p-> data == item)
        {
            cout << "Duplicate Data" << endl;
        }
        else 
        {
            if (item < q->data)
            {
                q->lchild = new_node;
            }
            else
            {
                q->rchild = new_node;
            }
        }

    }
}

Главный:

#include "Tree.h"

int main()
{
    //variables for data
    string file;
    ifstream infile(file);
    Tree<int> myTree;
    int d = 0;

    //ask user to enter filename
    cout << "Please enter the file you wish to open: " << endl;
    getline(cin, file);
    infile.open(file.c_str());

    //make sure filename is valid
    while (!infile)
    {
        cout << "Error opening file, please enter the name of the file you wish to open: " << endl;
        getline(cin, file);
        infile.open(file.c_str());
    }

    //if file is good, build tree
    while (!infile.eof())
    {
        myTree.insert(d);
        infile >> d;
        cout << d << endl;
    }

    system("PAUSE");
    return 0;
}

person user5407906    schedule 25.10.2015    source источник
comment
не вставляйте .cpp файл !!!   -  person    schedule 25.10.2015
comment
@GRC Ах. Я сделал это изначально, потому что продолжал получать неразрешенные ошибки внешних символов ...   -  person user5407906    schedule 25.10.2015
comment
@GRC Похоже, что ошибки связаны с моим корневым объявлением, потому что они отображаются в функции вставки, конструкторе по умолчанию и деструкторе.   -  person user5407906    schedule 25.10.2015
comment
включите также ваш файл .h.   -  person    schedule 25.10.2015
comment
@GRC Я не знаю, имеет ли это значение, но конкретная ошибка говорит: ошибка LNK2019: неразрешенный внешний символ public: void __thiscall Tree ‹int› :: insert (int) (? Insert @? $ Tree @ H @@ QAEXH @ Z), на который есть ссылка в функции _main   -  person user5407906    schedule 25.10.2015
comment
@GRC Я неправильно создаю объект дерева в основном?   -  person user5407906    schedule 25.10.2015
comment
Ошибка - это ошибка microsoft, я не могу ее воспроизвести, меня немного смущают шаблоны, так как я не использовал их в течение длительного времени.   -  person    schedule 26.10.2015
comment
@GRC Я ценю ваше время и помощь, в итоге я просто создал класс, не являющийся шаблоном, и теперь это не дает мне этой ошибки.   -  person user5407906    schedule 26.10.2015


Ответы (2)


У вас есть несколько проблем с вашим алгоритмом, я укажу на некоторые из них.

if (root == nullptr)
{
    root = new_node;
}

заботится о том, чтобы root не был нулевым. Вниз по коду, который у вас есть

Node<Item> *p = root;

а также

while (p != nullptr && p->data != item)

одна ошибка здесь уже указана в другом ответе, но p не может быть нулевым, поскольку в этот момент p совпадает с root, а p никогда не меняется, поэтому вы постоянно указываете на root.

q = p // I would do q = root;

должен быть вне цикла. Внутри петель должно быть что-то вроде этого:

while(q != nullptr) {
  if(newNode->data < q->data) {
    q = q->leftChild;
  } else if(newNode->data > q->data) {
    q = q->rightChild;
  } else {
    cout << "ERROR: item already exists";
    return 1;
  }
}
person Community    schedule 25.10.2015
comment
Я попробовал ваш код, и он отлично распечатал список (все еще без повторяющихся сообщений), но, поскольку я смотрю свои локальные переменные, в p ничего не сохраняется, потому что ничего не сохраняется в корне. Дерево строится неточно. Есть идеи, почему? - person user5407906; 25.10.2015
comment
где вы объявляете Node<Item> root он говорит Node<Item> root = nullptr - person ; 25.10.2015
comment
Да, я редактирую свой исходный пост, чтобы добавить свои конструкторы и тому подобное. - person user5407906; 25.10.2015
comment
Можете ли вы также опубликовать свой основной метод? - person ; 25.10.2015

В условии цикла while не должно быть

while (p != nullptr && p->data != item)

q - это просто нулевой указатель, и [q-> data! = item] всегда будет истинным.

person Aditya Shekhawat    schedule 25.10.2015