c++ error LNK2019: binary search tree

Question

Thinking there is an issue with my root declaration, the three errors are showing up in my insert function, default constructor and destructor.

If I #include .cpp file: There is an issue with my insert function and constructing the tree properly. I am watching my local variables and root is behaving strangely - after the first value is added root is pointing to something that has no data. (I'm quite new to C++ so please bear with me, this is my first time creating a template class & a binary search tree)

It's throwing an exception each time it reaches the line while(p->data != item).

Here's my insert function:

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

Header:

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

And here is my Tree class:

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

    }
}

Main:

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

Answer 1

You have several problems with your algorithm, I will point to few of them.

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

takes care of condition that root is not null. Down the code you have

Node<Item> *p = root;

and

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

one error here is already pointed in another answer but p cannot be null since at this point p is same as root and p is never changing, so you are constantly pointing at root.

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

should be outside the loop. Inside of loops should be something like this:

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

Answer 2

In the while loop condition shouldn't it be

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

q is just a null pointer and [ q->data != item ] will always be true.