Remote Training on Programming

Создайте иерархию классов, изображенную на следующем рисунке:

 

Базовый класс Tree описывает структуру данных "упорядоченное дерево" в общем виде.

Классы-наследники соответствуют двум вариантам реализации:

• LR_Tree – на основе представления «левый сын-правый брат»
• Ar_Tree – указатели на детей для каждого узла хранятся в массиве внутри него

 

Классы имеют следующий интерфейс:

//базовый класс дерево
class Tree
{
public:

  // тип данных для вершин дерева
  struct Node
  {
    int data; //некие данные, хранящиеся в узлах (например, номера)
    friend class Tree;
    //виртуальный деструктор - для корректного удаления потомков
    //через указатели на предков
    virtual ~Node(){};
  };


protected:

  //корень дерева
  Node *_root;

public:

  Tree(void);
  virtual ~Tree(void);

  //количество узлов в дерево
  int size(void) const;

  //возвратить указатель на корень дерева
  Node* root(void);

  //----виртуальные абстрактные функции - здесь описывается только их вид,
  //а реализовываться они будут по-разному в классах-наследниках-----

  //возвратить первого сына узла n
  virtual Node* first_child(const Node *n) const=0;

  //возвратить следующего сына узла n
  virtual Node* next_child(const Node *n, const Node *c) const=0;

  //возвратить родителя узла n
  virtual Node* parent(const Node *n) const=0;

  //создать нового сына для узла parent, поставить его в конец других
  //детей (для упрощения проверки :-) ) и возвратить указатель на него
  //если создаётся новый корень, то указывается parent=NULL
  virtual Node* new_node(Node *parent) = 0;

  //удалить поддерево с корнем в указанной вершине
  virtual void delete_subtree(Node *node) = 0;

  //----функции обхода деревьев - реализуйте посредством вызова виртуальных функций----

  //тип данных - указатель на функцию пользователя
  typedef void (*userfunc) (Node *node, int level);

  //выполнить обход в глубину, для каждого узла вызвать функцию f,
  //куда передать узел и его глубину
  //дети каждого узла должны перебираться в том порядке, в каком они хранятся 
  void dfs(userfunc f);

  //выполнить обход в ширину, для каждого узла вызывать функцию f
  //куда передать узел и его глубину
  //дети каждого узла должны перебираться в том порядке, в каком они хранятся
  void bfs(userfunc f);

  //-----функции класса-----
  static int trees_count(void) {//количество деревьев, в данный момент созданных в программе
    return trees_cnt;
  }

private:

};

///////////////////////////////////////////////////////////////////
//конкретная реализация №1 - представление "левый сын-правый брат"
///////////////////////////////////////////////////////////////////
class LR_Tree : public Tree
{

public:

  struct LR_Node : public Node
  {
    //расширьте структуру так, как считаете нужным
  };

  //выполните реализации всех виртуальных функций, описанных в базовом классе
  virtual Node* first_child(const Node *n) const;
  virtual Node* next_child(const Node *n, const Node *c) const;
  virtual Node* parent(const Node *n) const;
  virtual Node* new_node(Node *parent);
  virtual void delete_subtree(Node *node);

  //создайте необходимые конструкторы, деструктор, перегрузите операцию присваивания
  LR_Tree& operator= (const LR_Tree &r); //операция присваивания
  LR_Tree(void){};
  LR_Tree(const LR_Tree &r); //копировщик
  virtual ~LR_Tree(void); //деструктор

};

/////////////////////////////////////////////////////////////
//конкретная реализация №2 для не сильно ветвистых деревьев -
//в каждом узле хранится массив указателей на детей
/////////////////////////////////////////////////////////////
class Ar_Tree : public Tree
{
public:

  struct Ar_Node : public Node
  {
    //расширьте структуру так, как считаете нужным
  };

  //конструктор, в качестве параметра принимающий максимальную "ветвистость"
  //дерева, т.е. размер массивов детей в узлах дерева
  Ar_Tree(int branchiness);

  //выполните реализации всех виртуальных функций, описанных в базовом классе
  virtual Node* first_child(const Node *n) const;
  virtual Node* next_child(const Node *n, const Node *c) const;
  virtual Node* parent(const Node *n) const;
  virtual Node* new_node(Node *parent);
  virtual void delete_subtree(Node *node);

  //создайте деструктор, перегрузите операцию присваивания и др., если что ещё нужно

  Ar_Tree(const Ar_Tree &r); //копировщик
  virtual Ar_Tree::~Ar_Tree(void);   //деструктор
  Ar_Tree& operator= (const Ar_Tree &r); //операция присваивания

};


//во все классы можно добавлять любые недостающие данные
//(желательно только в разделы private и protected)

//это должно стоять в конце вашего кода при отправке в систему
#include "trees-test.h"

//ваш код не должен содержать функцию main

Пример проверок, которые будут выполняться над вашим классом:

//простой вывод в строчку
void myfunc1(Tree::Node *node, int level)
{
  cout << node->data << " ";
}

void test1(void){

  Tree* trees[2]; //массив из нескольких деревьев

  //создаём сильноветвящееся дерево, заполняем в нём пару уровней
  trees[0] = new LR_Tree;
  Tree::Node *root = trees[0]->new_node(NULL); root->data = 1;
  for (int i=2; i<=4; i++)  {
    Tree::Node *node = trees[0]->new_node(root);
    node->data = i;
    for (int j=1000; j<=1001; j++)
    {
      Tree::Node *node2 = trees[0]->new_node(node);
      node2->data = j;
    }
  }

  //создаём не очень ветвящееся дерево, заполняем несколько уровней
  trees[1] = new Ar_Tree(3);
  Tree::Node *root2 = trees[1]->new_node(NULL); root2->data = 1;
  for (int i=2; i<=3; i++)  {
    Tree::Node *node = trees[1]->new_node(root2);
    node->data = i;
    for (int j=4; j<=6; j++)
    {
      Tree::Node *node2 = trees[1]->new_node(node);
      node2->data = j;
    }
  }

  //выполняем разные обходы и выводим их на экран разными способами
  for(int i=0; i<2; i++)
  {
    trees[i]->dfs(myfunc1); cout << endl;
    trees[i]->bfs(myfunc1); cout << endl;
  }

  //проверяем, как работает перечисление сыновей узла
  for(int i=0; i<2; i++) {
    Tree::Node *root = trees[i]->root();
    Tree::Node *node = trees[i]->first_child(root);
    while (node!=NULL)
    {
      cout << node->data << " ";
      node = trees[i]->next_child(root,node);
    }
    cout << endl;
  }

  //проверяем, как работает удаление поддеревьев
  for(int i=0; i<2; i++)
  {
    Tree::Node *node = trees[i]->first_child(trees[i]->root());
    trees[i]->delete_subtree(node);
    trees[i]->bfs(myfunc1); cout << endl;
  }

  //удаляем деревья
  for(int i=0; i<2; i++)
    delete trees[i];

}

Пример результата, который должен получиться:

1 2 1000 1001 3 1000 1001 4 1000 1001 
1 2 3 4 1000 1001 1000 1001 1000 1001 
1 2 4 5 6 3 4 5 6 
1 2 3 4 5 6 4 5 6 
2 3 4 
2 3 
1 3 4 1000 1001 1000 1001 
1 3 4 5 6