c++ - 指向两种不同类型节点的指针

Question

我正在用 C++ 编写哈希树，其中我需要两种不同类型的节点，即一种用于非叶节点，它将简单地指向其子节点，另一种用于包含所需信息的叶节点。

我面临的问题是如何在非叶节点中声明指针。因为有些非叶子节点要指向其他非叶子节点，有些必须指向叶子节点。所以我不能为非叶节点中的指针声明一种指针类型。

任何帮助，将不胜感激。

Answer 1

您可以只拥有一个带有数据指针的节点类，而不是拥有一个叶节点和一个非叶节点。如果节点不是叶节点，则数据指针将为NULL。如果节点是叶节点，Node*则将是NULL。

struct Node
{
    Node *child; // NULL if leaf node
    Data *data;  // NULL if not leaf node
};

Answer 2

我会在标题中使用联合和标志来处理这个问题，告诉我所讨论的指针是指向节点还是叶。

struct Header
{
   int isLeaf;
}

struct Leaf
{
    struct Header header;
    struct LeafBody body;
}

struct Node
{
    struct Header header;
    struct NodeBody body;
}

union Entity
{
    struct Header header;
    struct Node   node;
    struct Leaf   leaf;
}

Answer 3

有几种解决方案。您可以简单地从叶子继承非叶子，并让多态性处理它。或者使用联合和标志来确定使用哪个。或者最肮脏但有时是有效的，是一个简单的 void*，您可以随时将其转换为您需要的任何东西。根据您的特定需求：联合将表现最佳，多态性将最易读，并且 void* 将与联合具有相同的性能，并且如果您不喜欢联合，则取决于口味更清晰的代码。