C语言 有权访问继承结构的结构

Question

我正在尝试编写一些函数来处理平衡的二叉树。

首先，我编写了一个典型的二叉树接口。这封装了与二叉树相关的常规功能。

树有节点

typedef struct Node
{
Node* left;
Node* right;
Node* parent;
int key;
void* value;
} Node;

以及一些insert、remove和search的功能。

现在我想扩展该接口以处理不同类型的二叉树，它继承了Node。

typedef enum Color
{
RED,
BLACK
} Color;
typedef struct RBTreeNode
{
Node* genericNode;
Color color;
} RBTreeNode;

RBTree指红黑树

当我尝试编写"树修复"函数时，麻烦随之而来。

void repairRBTree(Node* nodeInserted)
{
// If nodeInserted's parent is NULL, nodeInserted is the root of the tree.
// Red-Black tree properties suggest root node's color be black.
if (nodeInserted->parent == NULL)
{
RBTreeNode* nodeInsertedTC = (RBTreeNode*)nodeInserted;
nodeInsertedTC->color      = BLACK;
}
// If nodeInserted's parent's color is BLACK, nodeInserted has replaced a RED NULL node.
// Red-Black tree properties suggest RED node's parent be BLACK,
// which is the case currently, so there's nothing to be done.
else if (nodeInserted->parent->(COLOR??))
{
return;
}
}

在这份if声明中，

if (nodeInserted->parent == NULL)
{
RBTreeNode* nodeInsertedTC = (RBTreeNode*)nodeInserted;
nodeInsertedTC->color      = BLACK;
}

如果我之前将nodeInserted转换为Node*，这意味着指针本身是一个RBTreeNode*，所以如果我的想法是正确的，那么将其投射回RBTreeNode*应该做我认为应该做的事情。

但在这里

// If nodeInserted's parent's color is BLACK, nodeInserted has replaced a RED NULL node.
// Red-Black tree properties suggest RED node's parent be BLACK,
// which is the case currently, so there's nothing to be done.
else if (nodeInserted->parent->(COLOR??))
{
return;
}
}

我无法访问nodeInserted->parent的Color枚举。而且我不认为把它投给RBTreeNode会有多大好处。

我知道唯一可行的解决方案是重写所有广义函数以将RBTreeNode作为参数而不是Node，但我真的不想这样做。

有没有更好的解决方案？

Answer 1

不应使用指针来实现继承。使用Node字段而不是指针：

typedef struct RBTreeNode
{
Node genericNode;
Color color;
} RBTreeNode;

这样，当您将Node*投射到RBTreeNode*时，它将可以访问RBTreeNode的所有字段。

由于您可能使用的是 c++ 编译器，因此 c++ 类比可能会有所帮助。拥有Node类型的第一个字段就像在 c++ 中具有继承性，即struct RBTreeNode: Node.拥有指针类型的第一个字段就像拥有虚拟继承，即struct RBTreeNode: virtual Node.这两种方式都有效，直到你需要一个沮丧。C++ 中的虚拟继承会提醒读者，你的继承层次结构("菱形继承"(有一些可疑之处，所以你应该只在正常继承不起作用时才使用它。