0

好吧,我尝试通过网络寻找解决方案,但找不到任何解决我问题的方法。

我正在为班级写一个作业,让我们使用模板进行二叉树搜索。我已经在之前的课程中构建了一个整数二叉搜索树,所以这主要是同一个程序,只是做了一些调整(最重要的是模板)。上一课中的程序运行得非常好,但是在应用模板之后,它给了我一组非常奇怪的错误:

1>tester.obj : error LNK2019: unresolved external symbol "public: __thiscall binTree<int>::~binTree<int>(void)" (??1?$binTree@H@@QAE@XZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::deleteNode(int const &)" (?deleteNode@?$binTree@H@@QAEXABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: bool __thiscall binTree<int>::find(int const &)" (?find@?$binTree@H@@QAE_NABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: int __thiscall binTree<int>::height(void)" (?height@?$binTree@H@@QAEHXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::postorderTraversal(void)" (?postorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::preorderTraversal(void)" (?preorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::inorderTraversal(void)" (?inorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::insert(int const &)" (?insert@?$binTree@H@@QAEXABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: __thiscall binTree<int>::binTree<int>(void)" (??0?$binTree@H@@QAE@XZ) referenced in function _main

我的代码在 BTS 类的标头、带有函数的 cpp 文件和 cpp 测试器之间分解。

BinTree.h:

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

//***** FUNCTION DESCRIBED BRIEFLY IN CPP FILE 
template<class T>
class binTree
{
    //the node struct
    struct btnode   {
        T info;
        btnode* left;
        btnode* right;
                    };
    private:
        btnode* root; //the root
        void remove(btnode* &node);
        int heightRecursive(btnode *node);
        void destroyRecursive(btnode*);
        bool leaf(btnode* node) const;
        //    recursive traversals 
        void inorderRecursive(btnode* node);
        void preorderRecursive(btnode* node);
        void postorderRecursive(btnode* node);
    public:
        binTree(void);
        int height();
        void insert(const T &inData);
        bool find (const T &inData);
        void deleteNode(const T &inData);
        ~binTree(void);

        //    traversal
        void inorderTraversal();
        void preorderTraversal();
        void postorderTraversal();
    };

BinTree.cpp:

#include "BinTree.h"

//constructor, sets the root equal to NULL
template<class T> binTree<T>::binTree(void)
{
root = NULL;
}
//inserts into the tree; if the tree is empty, it inserts to the root
// if the tree already has the variable, it outputs a message and exits
// other wise, it will search for an appropiate place to fit the variable in
template<class T> void binTree<T>::insert(const T &inData)
{
    btnode *newnode, *current, *parentOfCurrent;
    newnode = new btnode;
    newnode->info = inData;
    newnode->left = newnode->right = NULL;

    if (root == NULL)   {
        root = newnode;
        cout << "added to root\n";
        return;         }
    current = root;
    while(current != NULL)  {
    parentOfCurrent = current;
        if(current->info == inData)
        {
            cout << inData << " already exists in tree. Duplicates not allowed!\n";
            return;
        }
        else if(current->info > inData)
            current = current->left;
        else
            current = current->right;
                            }

    if (parentOfCurrent->info > inData)
        parentOfCurrent->left = newnode;
    else
        parentOfCurrent->right = newnode;

}
//--------------- inorder traversal ----------------------
//calls the inorderTraversal using the root
template <class T> void binTree<T>::inorderTraversal()
{
if(root==NULL)
    cout << "Empty tree\n";
    else    {
        inorderRecursive(root);
        cout << '\n';
            }
}
//Private variable, travels recursively in inorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::inorderRecursive(btnode* node) //left, node, right
{
if(node != NULL)    {
    inorderRecursive(node->left);
    cout << node->info << ", ";
    inorderRecursive(node->right);
                    }
}
//------------------ preorder traversal-------------
//calls the preOrderTraversal using the root
template <class T> void binTree<T>::preorderTraversal()
{
    if(root==NULL)
        cout << "Empty tree\n";
    else    {
        preorderRecursive(root);
        cout << '\n';
            }
}
//Private variable, travels recursively in preorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::preorderRecursive(btnode* node) //node, left, right
{
    if(node != NULL)    {
        cout << node->info << ", ";
        preorderRecursive(node->left);
        preorderRecursive(node->right);
                        }
}
//------------ postorder traversal-----------------
//calls the postOrderTraversal using the root
template <class T> void binTree<T>::postorderTraversal()
{
    if(root==NULL)
        cout << "Empty tree\n";
    else    {
        postorderRecursive(root);
        cout << '\n';
            }
}
//Private variable, travels recursively in postorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::postorderRecursive(btnode* node) 
{
    if(node != NULL)    {
        postorderRecursive(node->left);
    postorderRecursive(node->right);
    cout << node->info << ", ";
                        }
}
//-------
//searches the tree and returns either true or false if found or not found
template<class T> bool binTree<T>::find(const T &inData)
{
    bool rv = false;
    btnode *current;
    if(root == NULL)
        return rv;
    current = root;
    while(current != NULL && rv == false)
    {
        if (current->info == inData)
            rv = true;
        else if (current->info > inData)
            current = current->left;
        else
            current = current->right;
    }
    return rv;
}
//deletes a node using the remove function. If the tree is empty or the variable
// is not found, it will send a message and abort. 
template <class T> void binTree<T>::deleteNode(const T &inData)
{
    btnode *current, *parentOfCurrent;
    bool found = false;
    if (root == NULL)   {
        cout << "The tree is empty, aborting...";
        return;
                        }
    current = root;
    while(current != NULL)
    {
        if(current->info == inData) {
            found = true;
            break;
                                    }
        else    {
            parentOfCurrent = current;
            if(current->info > inData)
                current = current->left;
            else
                current = current->right;
                }
    }
    if(!found)
        cout << "\n" <<inData << " could not be found. Aborting...\n";
    else if (current == root)
        remove(root);
    else if (parentOfCurrent->info > inData)
        remove(parentOfCurrent->left);
    else
        remove(parentOfCurrent->right);
}
//
template <class T> void binTree<T>::remove(btnode* &node) // parent's node with address of
//node to be deleted. Sent in by ref. So parent's node changed here
{
    btnode *current, *parentOfCurrent, *temp;
    if(node==NULL)  {
        cout << "\nCannot delete NULL node.\n";
        return; //the return is here because if the node is NULL, then it is also technically a leaf
                    }
    else if(leaf(node) == true) //node is a leaf
    {
    temp = node;
    node = NULL;
    delete temp;
    }
    else
        cout << "\nNode is not a leaf, cannot delete.\n";

}
//finds the height of the tree by passing root into the heightRecursive function
template <class T> int binTree<T>::height()
{
    return heightRecursive(root);
}
//recursively travels the tree and keeps a counter each time it encounters a node 
template <class T> int binTree<T>::heightRecursive(btnode* node)
{
    if (node == NULL)
        return 0;
    else
        return ( 1 + max(heightRecursive(node->left), heightRecursive(node->right)));
}
//destryuuctor; it calls the destroyRecursive function using root
template <class T> binTree<T>::~binTree(void)
{
    destroyRecursive(root);
}
//travels the tree recursively, deleting every non-Null it encounters 
template <class T> void binTree<T>::destroyRecursive(btnode* node)
{
if(node != NULL)    {
    destroyRecursive(node->left);
    destroyRecursive(node->right);
    delete node;
    node = NULL;
                    }
}
//checks if the node passed as an argument is a leaf, returns true or false
template <class T> bool binTree<T>::leaf(btnode* node) const
{
    bool aLeaf = false;
    if(node->left == NULL && node->right == NULL)
        aLeaf = true;
    return aLeaf;
}

测试仪.cpp:

#include "BinTree.h"

int main()
{
    binTree<int> example;
    int arr[] = { 75,43,77,29,52,82,35,56,79,32,40,90,48,47 };

    //inserts the array of integers into the tree
    for(int i=0; i < 14; i++)
        example.insert(arr[i]);

    //---------------Displays tree before changes-------------------
    cout << "In order traversal:\n";
    example.inorderTraversal();

    cout << "Pre-order traversal:\n";
    example.preorderTraversal();

    cout << "Post-order traversal:\n";
    example.postorderTraversal();

    cout << "------------------Displays tree after changes---------------------\n";
    example.insert(21);

    cout << "\n------- inorder --------\n";
    example.inorderTraversal();

    cout << "\n------- preorder --------\n";
    example.preorderTraversal();

    cout << "\n------- postorder --------\n";
    example.postorderTraversal();

    cout << "\nheight=" << example.height() << endl<<endl;

    //tests the find function
    if (example.find(9))
        cout << "found 9\n";
    else
    cout << "9 not found\n";

    if (example.find(77))
        cout << "found 77\n";
    else
        cout << "77 not found\n";

    //tests the delete function by trying to delete an integer not in the tree
    example.deleteNode(122);

    //test the insert by inserting already existent integer
    example.insert(77);

    //tests the delete function by deleting 77
    example.deleteNode(77);
    cout << "\nAfter deleting 77 (inorder)\n";
    example.inorderTraversal();

    system("pause"); //don't worry, the system call will be gone in the final submission
    return 0;
}

正如我之前所说,我很确定这与我在模板实现中做错了什么有关。如果是模板,我能得到确切的代码片段吗?应该实现什么?我对模板相当陌生,所以这让我有点头疼。如果有帮助,我会使用 Visual Studios 2010。

4

1 回答 1

4

在这里你知道它为什么不起作用:将 模板化的 C++ 类拆分为 .hpp/.cpp 文件——这可能吗?

TL;DR:您不能在 .h 和 .cpp 文件之间拆分模板类,将实现移动到 .h 文件。

于 2013-04-06T00:33:53.707 回答