Структура с доступом к унаследованной структуре - PullRequest
Новая
       16

Структура с доступом к унаследованной структуре

1 голос
/ 09 февраля 2020

Я пытаюсь написать некоторые функции для работы на сбалансированном двоичном дереве.

Сначала я написал типичный интерфейс двоичного дерева. Это инкапсулирует общую функциональность, связанную с двоичными деревьями.

В дереве есть узлы 

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, но я действительно не хочу этого делать.

Есть ли лучшее решение?

1 Ответ

0 голосов
/ 09 февраля 2020

Вы не должны использовать указатель для реализации наследования. Используйте поле Node вместо указателя: 

typedef struct RBTreeNode
{
  Node genericNode;
  Color color;

} RBTreeNode;

Таким образом, когда вы преобразуете Node* в RBTreeNode*, оно будет иметь доступ ко всем полям RBTreeNode.

Поскольку вы, вероятно, используете компилятор c ++, может помочь аналогия с ++. Наличие первого поля типа Node похоже на наследование в c ++, т.е. struct RBTreeNode: Node. Наличие первого поля типа указателя похоже на виртуальное наследование, т.е. struct RBTreeNode: virtual Node. Оба способа работают, пока вам не понадобится уныние. Виртуальное наследование в c ++ предупреждает читателя, что у вас есть что-то подозрительное в вашей иерархии наследования («наследование бриллиантов»), поэтому вы должны использовать ее только тогда, когда обычное наследование не подходит.

...