c++ - 使用 cpp 将节点插入二叉搜索树

Question

我在尝试将节点插入二叉搜索树时遇到问题。我不断得到

错误 LNK2019：未解析的外部符号“public：__thiscall tr​​ee::tree(void)”(??0?$tree@H@@QAE@XZ)

有人可以告诉我问题是什么。

树节点.h

template <class T> class tree;

//treenode class-template definition
template <class T>
class treenode
{
friend class tree<T>;

public:

    treenode(const T &d, treenode<T> *l, treenode<T> *r)
        : data(d), leftptr(l), rightptr(r)
    {

    }

    treenode(const T &d):
        leftptr(0),
        data(d),
        rightptr(0)
    {

    }

    T getData() const
    {
        return data;
    }

private:
    treenode<T> *leftptr;
    T data;
    treenode<T> *rightptr;
};//end class treenode

树.h

class tree
{
public:
    tree(); //initializes the private data member

    void insertNode (treenode<T> **, const T &);
    void preOrderTraversal(treenode<T> * ) const;
    void postOrderTraversal(treenode<T> * ) const;
    void inorderTraversal(treenode<T> *) const;

private:
    treenode<T> *rootptr;
};

树.cpp

#include <iostream>
#include "tree.h"
using namespace std;

//constructor
template< class T>
tree<T>::tree()
{
rootptr = 0; //indicate tree is initially empty
}//end tree constructor


//insert node in tree
template <class T>
void tree<T>::insertNode(treenode<T> **rootptr, const T &val)
{
// subtree is empty; create new treenode containing value
if(*rootptr == 0)
    *rootptr = new treenode<T>(val);
else // subtree is not empty
{
    // data to insert is less than data in current node
    if(val < (*rootptr)->data)
    {
        insertNode(&((*rootptr)->leftptr), val);
    }
    else
    {
        // data to insert is greater than data in current node
        if(val > (*rootptr)->data)
        {
            insertNode(&((*rootptr)->rightptr), val);
        }
    }//end else
}//end else
}//end function insertNode

测试器.cpp

int main()
{
   tree <int> create;
   int userVal;

   cout << "Enter 10 Integers" << "\n\n";
   for(int i=0; i<10; i++)
{
    cout << "-> ";
    cin >> userVal;
    createTree.insertNode(0, userVal);
    }

   system("pause");
   return 0;
}//end main

Answer 1

问题是头文件tree中没有定义构造函数。tree.h编译器需要模板的完整定义才能实例化它。现在，发生的情况是某个文件包含 tree.h，编译器看到该类的类定义，tree但找不到其构造函数的定义。

因此，您需要将 tree.cpp 文件中的所有内容移动到 tree.h 中。（这不适用于普通的非模板类。）

它实际上比这稍微复杂一些： Storing C++ template function definitions in a .CPP file

因此，您可以将定义放在 .cpp 文件中，但前提是您为要使用的所有类型显式实例化模板。最简单的解决方案仍然是将整个定义放在头文件中。