B+树节点实现

Question

我正在为一个类实现一个B+Tree。当前节点的实现方式如下：

class Node {
    public:
        E* keys[order*2];
        Node *children[order*2+1];
        int size;
        Node(){ 
            size = 0;
        }
        bool empty() {
            return size == 0;
        }
        bool isLeafNode() {
            return false;
        }
};

class LeafNode : public Node {
    public:
        E* data[order*2+1];
        bool isLeafNode() {
            return true;
        }
};

当我想要向叶节点添加一个元素(通过访问LeafNode->data)时，我得到

 error: request for member ‘data’ in ‘left<int>’, which is of non-class type ‘BTree<int>::LeafNode*()’

我猜这是因为编译器不知道我正在访问的节点是内部节点还是叶节点，尽管我首先使用isLeafNode()进行了检查。我不能将这两个类合并为一个，因为Leaf节点需要比内部节点多一个Bucket来存储数据。

我知道这是一个设计问题，但是有没有一些我遗漏的解决这个问题的微不足道的方法呢？我对C++还是个新手。

Answer 1

对于这样的事情，你真的应该使用虚拟方法。您可以更改isLeafNode()查询，使其返回指向叶节点的指针(如果是叶节点)，否则返回NULL。

class LeafNode; // forward declare

class Node {
//...
public:
    virtual ~Node () {}
    virtual LeafNode * isLeafNode () { return 0; }
    //...
};

class LeafNode : public Node {
//...
public:
    LeafNode * isLeafNode () { return this; }
    //...
};

然后，如果data实际上是LeafNode，则可以从Node使用此方法来访问它。

Answer 2

错误消息

error: request for member ‘data’ in ‘left<int>’, which is of non-class type  ‘BTree<int>::LeafNode*()’

这种形式的其他错误通常意味着您试图使用.访问struct的字段，而实际上您应该使用->。例如，如果您有

LeafNode* ptr = /* ... */;
ptr.data[0] = /* ... */;

您将在第二行得到一个错误，因为您使用的是.而不是->。

尝试查看这是否是您在指示线上遇到的错误，如果是，请将点更改为箭头。

希望这能有所帮助！