时间戳

首页 > 解决方案 > 可以访问继承结构的结构

c - 可以访问继承结构的结构

问题描述

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

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

树有节点

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*，这意味着指针本身是 a 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'sColor枚举。而且我认为将其转换为RBTreeNode不会有多大好处。

我知道唯一可行的解​​决方案是，如果我重写所有通用函数以RBTreeNode作为 param 而不是Node，但我真的不想这样做。

有更好的解决方案吗？

标签： cinheritancelinked-liststructurenodes

解决方案

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

typedef struct RBTreeNode
{
  Node genericNode;
  Color color;

} RBTreeNode;

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

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

推荐阅读