2013-05-12 3 views
0

Я работаю над шаблоном для двоичного дерева поиска, и я получаю сообщение об ошибке ниже. Я знаю, что есть похожие сообщения, но я не могу понять эту штуку. Шаблоны, безусловно, являются слабым предметом для меня, поэтому я думаю, что мне не хватает фундаментальной семантической вещи, но я могу на нее наложить. Ниже приведена ошибка, чем после того, как файлы программы. Если бы кто-нибудь мог указать мне в правильном направлении, я был бы очень признателен.Шаблонное дерево двоичного поиска C++, нерешенная внешняя ошибка

Ошибка 1 Ошибка LNK2019: неразрешенный внешний символ "частное: BOOL __thiscall Tree :: insertHelper (класс TreeNode * &, целое)" (insertHelper @ $ Tree @ H @@ AAE_NAAPAV $ TreeNode @ H @?? @ H @ Z), на которые ссылается функция «public: bool __thiscall Tree :: insert (int)» (? Insert @? $ Tree @ H @@ QAE_NH @ Z) C: \ Users \ wm \ documents \ visual studio 2012 \ Projects \ BinaryTree \ BinaryTree \ main.obj

-базисной основной для тестирования

#include "BinarySearchTree.h" 
#include "TreeNode.h" 
#include <iostream> 

using namespace std; 

int main() 
{ 
    Tree<int> test; 
    test.insert(55); 

    return 0; 
} 

-tree шаблон

#include <iostream> 
#include "TreeNode.h" 

using namespace std; 

template< class ItemType > 
class Tree { 
public: 

    Tree(); 
    ~Tree();  
    bool isEmpty() const; 
    void makeEmpty(); 
    bool insert(ItemType newItem); 
    bool retrieve(ItemType searchItem, ItemType & foundItem); 
    bool deleteItem (ItemType deleteItem); 
    void print(); 

private: 

    TreeNode<ItemType> * rootPtr; // pointer to the root 

    //utility functions 
    void printHelper(TreeNode<ItemType> *); 
    bool insertHelper(TreeNode<ItemType> * & node, ItemType item); 
    bool deleteHelper(TreeNode<ItemType> * & , ItemType); 
    void deleteNode(TreeNode<ItemType > * &); 
    bool retrieveHelper(ItemType, TreeNode<ItemType> * & , ItemType &); 

}; 

template<class ItemType> 
Tree<ItemType>::Tree() 
{ 
    rootPtr = NULL; 
} 
template<class ItemType> 
Tree<ItemType>::~Tree() 
{ 
    makeEmpty(); 
} 
template<class ItemType> 
bool Tree<ItemType>::isEmpty() const 
//Returns True if the tree is empty, otherwise returns false 
//Postcondition: Tree is unchanged. 
{ 
    if(rootPtr == NULL) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 
template<class ItemType> 
void Tree<ItemType>::makeEmpty() 
//Makes the tree empty if it is not empty already. 
//Preconditions: The tree exists. 
//Postconditions: Tree is now empty. Any dynamically allocated memory which is no longer used is returned to the system. 
{ 
    return; 
} 
template<class ItemType> 
bool Tree<ItemType>::insert(ItemType newItem) 
// Inserts a copy of newItem in the tree. 
//Precondition: The tree exists and has binary search property. 
//Postcondition: if the tree already has an item where item == newItem, the function returns false and the trre is unchanged. 
//Otherwise, the newItem is inserted in the tree preserving and the binary search property is maintained. 
{ 
    if(rootPtr == NULL) 
    { 
     rootPtr->data = newItem; 

     return true; 
    } 
    else 
    { 
     return insertHelper(rootPtr, newItem); 
    } 
} 
template<class ItemType> 
bool insertHelper(TreeNode<ItemType> * & node, ItemType item) 
{ 
    if(item < node->data)//left 
    { 
     if(node->leftPtr == NULL) 
     { 
      node->leftPtr = new TreeNode<ItemType>(item); 
      return true; 
     } 
     else 
     { 
      return insertHelper(node->leftPtr,item); 
     } 
    } 
    else if(node->data < item)//right 
    { 
     if(node->righChild == NULL) 
     { 
      node->rightPtr = new TreeNode<ItemType>(item); 
      return true; 
     } 
     else 
     { 
      return insertHelper(node->rightPtr,item); 
     } 
    } 
    else// same value 
    { 
     return false; 
    } 
} 
template<class ItemType> 
bool Tree<ItemType>::retrieve(ItemType searchItem, ItemType & foundItem) 
// Given a searchItem, it tries to retrieve as foundItem, an item in the tree where the item == searchItem. 
// Precondition:The tree exists and has the binary search property. 
// Postcondition: If the tree already has an item where item == searchItem, foundItem is set to that item, and the function returns true. 
// If the tree has no such item, the function returns false and foundItem remains unchanged. The tree is unchanged. 
{ 

} 
template<class ItemType> 
bool Tree<ItemType>::deleteItem (ItemType deleteItem) 
// Given a deleteItem, it deltes from the tree any item where item == deleteItem. 
// Precondition: Tree exists and has binary search property. 
// Postcondition: If the tree has an item where item == deleteItem, that item is removed from the tree, and the function returns true, and 
// the binary search property is maintained. If the tree has no such item, the function returns false and the tree remains unchanged. 
{ 

} 
template<class ItemType> 
void Tree<ItemType>::print() 
// Prints the items in the tree in ascending order to the screen 
// Precondition: The tree exists and has binary search property. 
// Postcondition: The items have been printed in ascending order and the tree is unchanged 
{ 

} 
template<class ItemType> 
void printHelper(TreeNode<ItemType> *) 
{ 

} 
template<class ItemType> 
bool deleteHelper(TreeNode<ItemType> * & , ItemType) 
{ 

} 
template<class ItemType> 
void deleteNode(TreeNode<ItemType > * &) 
{ 

} 
template<class ItemType> 
bool retrieveHelper(ItemType, TreeNode<ItemType> * & , ItemType &) 
{ 

} 

-treenode

#ifndef TREENODE_H 
#define TREENODE_H 

template< class ItemType > class Tree; // forward declarations 

template<class ItemType> 
class TreeNode { 
    friend class Tree<ItemType>; // make Tree a friend 

public: 
    TreeNode(ItemType); // constructor 
    TreeNode();     // constructor with data uninitialized 
    ItemType getData() const;  // return data in the node 
private: 
    ItemType data;     
    TreeNode<ItemType> *leftPtr; 
    TreeNode<ItemType> *rightPtr; 
}; 

// Constructor 
template<class ItemType> 
TreeNode<ItemType>::TreeNode(ItemType newItem) 
{ 
    data = newItem; 
    leftPtr = NULL; 
    rightPtr = NULL; 
} 

template<class ItemType> 
TreeNode<ItemType>::TreeNode() 
{ 
    leftPtr = NULL; 
    rightPtr = NULL; 
} 


// Return a copy of the data in the node 
template< class ItemType > 
ItemType TreeNode<ItemType>::getData() const 
{ 
    return data; 
} 

#endif 
+0

Стоит отметить, что std :: set имеет те же свойства, что и дерево. В терминах insert/find/delete –

+0

PS: Когда вы его заработаете. Вы можете получить полный обзор кода. См. Http://codereview.stackexchange.com/ –

ответ

2

Хех. Проблема в том, что вы забыли оглавление квалификатора Дерево <ItemType> :: перед именем функции для insertHelper.

Просто сделай это:

template<class ItemType> 
bool Tree<ItemType>::insertHelper(TreeNode<ItemType> * & node, ItemType item) 

Кстати, ошибка линкер должен предложить вам, что это проблема. Прежде всего, вы знаете, что у вас проблема с ссылками, а не с компиляцией. Во-вторых, вы знаете символ, который не может быть найден. * Дерево <ItemType> :: * insertHelper (...). В-третьих, вы знаете, что вызов этой функции был успешно скомпилирован в Tree <ItemType> :: insert, что означает, что компилятор нашел и проанализировал объявление для метода insertHelper без проблем. Единственное возможное объяснение того, что компоновщик не может найти фактический объектный код для метода, состоит в том, что определение функции либо не существует, либо не имеет того же имени, которое вы объявили как!

1

Здесь:

if(rootPtr == NULL) 
{ 
    rootPtr->data = newItem; 

    return true; 
} 

Если rootPtr является NULL то rootPtr->data не является действительным.

Может быть, вы имели в виду:

if(rootPtr == NULL) 
{ 
    rootPtr = new TreeNode<ItemType>(newItem); 
} 
+0

Да, я просто поймал это. – wmurmann