红黑树模板

Question

我在实现使用模板的红黑树时遇到问题。我已经阅读并理解了目的，但不知道如何将它实现到头文件和 .cpp 文件中。我在一些论坛上读到它们必须与模板在同一个文件中，而其他人则说它们可以分开但在 .hpp 文件中。

头文件

enum nodeColor { RED, BLACK };

template <class myType>
struct nodeType
{

    myType  keyValue;
    nodeColor color;
    nodeType<myType> *left;
    nodeType<myType> *right;
    nodeType<myType> *parent;

};

template<class myType> 
class redBlackTree
{

public:
    redBlackTree() {}
    ~redBlackTree() {}
    void destroyTree();
    unsigned int countNodes() const;
    unsigned int height() const;
    void printTree() const;
    void insert(myType);
    bool search(myType);

private:
    bool search(myType, nodeType<myType> *);
    void destroyTree(nodeType<myType> *);
    unsigned int countNodes(nodeType<myType> *) const;
    unsigned int height(nodeType<myType> *) const;
    void printTree(nodeType<myType> *) const;
    void rightRotate(nodeType<myType> *);
    void leftRotate(nodeType<myType> *);

};

.cpp 文件

#include "redBlackTree.h"
using namespace std;

redBlackTree::redBlackTree()
{
}   
redBlackTree::~redBlackTree()
{
}
void redBlackTree::destroyTree()
{
}
unsigned int redBlackTree::countNodes() const
{
}
unsigned int redBlackTree::height() const
{
}
void redBlackTree::printTree() const
{
}
void redBlackTree::insert(myType)
{
}
bool redBlackTree<myType>::search(myType)
{
}

bool redBlackTree::search(myType, nodeType<myType> *)
{
}
void redBlackTree::destroyTree(nodeType<myType> *)
{
}
unsigned int redBlackTree::countNodes(nodeType<myType> *) const
{
}
unsigned int redBlackTree::height(nodeType<myType> *) const
{
}
void redBlackTree::printTree(nodeType<myType> *) const
{
}
void redBlackTree::rightRotate(nodeType<myType> *)
{
}
void redBlackTree::leftRotate(nodeType<myType> *)
{
}

我也知道我没有包含参数。我主要问的是如何解决这个问题，这样我就可以开始编码了。

Answer 1

有多种方法可以在 .cpp 文件中实现 class 模板，但最常见的方法是在 .hpp（或 .h）文件中实现它们。见 Why can templates only be implemented in the header file?.
更重要的是，你不能使用：
```
redBlackTree::redBlackTree()
{
} 
```
实现class模板成员函数。该语法只能使用 classes。您需要使用：
```
template <typename myType>
redBlackTree<myType>::redBlackTree()
{
} 
```
并对所有其他函数进行更改。

Answer 2

所有以任何方式使用 myType 的函数都需要在 .hpp 文件中。这是因为所有翻译单元都需要能够访问函数的完整定义才能实例化模板。

如果您想将它们保存在单独的文件中，您可以创建另一个 .hpp 文件，将定义放入其中，然后 #include 在您的第一个 .hpp 文件中。

有些人喜欢对这个实现文件使用不同的 file-ending，例如 .tcc。

红黑树模板

Red Black tree template

c++

templates

red-black-tree

binary-search-tree

data-structures