Создайте специальное двоичное дерево поиска, используя C ++ - PullRequest
Новая
       76

Создайте специальное двоичное дерево поиска, используя C ++

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

Я хочу создать двоичное дерево поиска, которое имеет специальные узлы. Должно быть три класса узлов, внутренний узел, внешний узел и узел Root, каждый из которых наследует общий родительский узел, и каждый тип узла будет иметь некоторую уникальную функцию. Возможно ли создать такой BST. Проблема, с которой я сталкиваюсь, состоит в том, что первый узел, который я вставляю в дерево, становится узлом root. Следующий узел, который я вставлю, станет Внешним Узлом. Теперь, если я вставлю другой узел, то внешний узел должен стать внутренним узлом, а новый узел станет внешним узлом. Также я не могу найти способ навигации по дереву от одного узла к другому, так как узлы будут разных типов. Можно ли создать дерево этого типа. Если да, то дайте мне несколько советов, как это можно сделать.

Ответы [ 2 ]

2 голосов
/ 15 февраля 2020

Если я правильно понимаю, вас беспокоит то, как объекты одного класса - Внешние - должны стать объектами другого класса - Внутренними. Это, когда C ++ является статически типизированным языком: типы (включая классы объектов) определяются во время компиляции. Правильно?

Ну, вы можете достичь этого по крайней мере одним из двух способов:

  1. Когда Внешний узел становится Внутренним, удалите Внешний узел и замените его Внутренним узлом, правильно инициализирован (например, чтобы указать на новый Внешний узел).
  2. Отказаться от Внешних и Внутренних, являющихся дискретными типами, и просто проверить, чтобы дети и родители определяли тип узла динамически.

Некоторые более подходящие материалы для чтения по этим вопросам:

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

Вы можете использовать базовое c наследование некоторых типов enum и рекурсивных вызовов. Это может быть отправной точкой: 

enum NodeType
{
    eRoot,
    eInternal,
    eExternal
};

class BinaryNode
{
public:
   virtual NodeType GetType() = 0;
   virtual void UpdateTree() = 0;

protected:
   BinaryNode* ChildLeft;
   BinaryNode* ChildRight;
   BinaryNode* Parent;
};

class ExternalNode : public BinaryNode 
{
   NodeType GetType() override { return eExternal; }
   void UpdateTree() override 
   { 
      //... Replace node instances here(e.g. delete this node and construct the correct new one given this sub tree. call new InternalNode(this) for example) 
      // Call this towards the parent node so the tree will be transformed accordingly
   }
}
class InternalNode : public BinaryNode 
{ 
   NodeType GetType() override { return eInternal; }
   void UpdateTree() override { //... }
}
class RootNode : public BinaryNode 
{ 
   NodeType GetType() override { return eRoot; }
   void UpdateTree() override { //... }
}

Это просто, чтобы дать вам представление, с чего начать. Вы можете проверить тип узла во время выполнения с помощью GetType () и выполнить некоторые проверки на основе этого.

Имейте в виду, что этот вид преобразования не особенно быстр. Если вы хотите, чтобы это было быстро, не используйте разные типы и вызовы виртуальных функций и указатели.

Поместите ваше двоичное дерево в массив и используйте двоичную индексацию, поэтому при заданном индексе «n» используйте 2*n+1, чтобы получить левого потомка, и 2*n+2, чтобы получить правого потомка. Затем используйте некоторые флаги (root, внешний, внутренний и c.), Чтобы определить, какие функции вы хотите вызвать на двоичном узле. Я бы не использовал наследование, как в моем примере кода, чтобы быть быстрым или более читабельным. Фактически, внешнее решение о том, какие функции вызывать на узле, может быть намного более читабельным и менее подверженным ошибкам.

...