具有访问继承结构的结构

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指的是Red-Black Trees

当我尝试编写“树修复”功能时出现了麻烦。

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

typedef struct RBTreeNode
{
  Node genericNode;
  Color color;

} RBTreeNode;

这样，当您将Node*转换为RBTreeNode*时，它将可以访问RBTreeNode的所有字段。

由于您可能正在使用c ++编译器，所以c ++类比可能会有所帮助。具有Node类型的第一个字段就像在c ++中具有继承关系，即struct RBTreeNode: Node。具有指针类型的第一字段就像具有虚拟继承，即struct RBTreeNode: virtual Node。两种方法都可以工作，直到您需要低调处理为止。 c ++中的虚拟继承警告读者，您对继承层次结构有些疑惑（“钻石继承”），因此，仅当常规继承不起作用时才应使用它。