Одна из многочисленных форм графа - деревья.

У любого дерева есть корень. Это узел расположенный в самом верху дерева. У дерева может быть только один корень.

К любому узлу дерева можно дойти из корня. Кроме того, существует только один путь связывающий корень и узел. Обратите внимание, что любой узел дерева сам по себе является деревом, назовём это дерево - поддеревом.

Расстояние от корня до узла называется уровнем. Корень расположен на нулевом уровне.

Если между узлами b и a есть дуга и узел a расположен на более высоком уровне, то a называется - родителем (parent), а b - сыном (son - сын, sons - сыновья). Все сыновья одного узла называются братьями. У узла дерева может быть любое количество сыновей.

Так как нас в деревьях интересует больше практический аспект, то более подробно деревья мы рассматривать не будем, а приступем к обзору реализации деревьев на C++.

Реализация класса деревьев

Для реализации мы создадим два класса: Tree и TreeIterator. Конечно же мы будем создавать шаблонные классы.

Обратим внимание на тот факт, что каждый узел дерева, сам является поддеревом. А это значит, что дерево - рекурсивная структура данных.

Класс дерева включает в себя переменную хранящую значение узла, указатель на родительский элемент и список сыновей. Для хранения списка сыновей мы воспользуемся классом DLinkedList.

template<class T>
class Tree
{
public:
  T data;
  Tree<T>* parent;
  DLinkedList<Tree<T>*> sons; // список указателей  на Tree<T>
  Tree<T> () : parent(NULL) {}
  ~Tree ();
};

data - переменная хранящая данные узла.

parent - указатель на родительский элемент. У корня данная переменная будет равна NULL.

sons - сыновья узла. Для хранения всех сыновей мы используем класс DlinkedList. Т.е. sons - список указателей, элементами которого являются деревья Tree.

Конструктор класса дерева

В списке инициализации конструктора полю parent присваивается NULL. Обратите внимание, так как для хранения сыновей используется связный список, то переменная sons проинициализируется в конструкторе DLinkedList.

Деструктор класс дерева

В деструкторе класса Tree используется рекурсия:

template<class T>
Tree<T>::~Tree ()
{
  DListIterator<Tree<T>*> itr(&sons, sons.head);
  Tree<T>* son = NULL;
  itr.Start();
  while (itr.Valid())
  {
    son = itr.node->data;
    sons.Remove(itr);
    delete son;
  }
}

Сначала мы получаем итератор списка сыновей текущего узла. Затем удаляем всех сыновей. Если какой-нибудь из узлов sons окажется поддеревом, то для него будет вызван деструктор. Сначала будут очищены самые нижние уровни ветвей, затем более высокие.

Вся остальная функциональность деревьев реализована в классе итераторов.

Реализация класса итераторов деревьев - TreeIterator

Для деревьев мы напишем свой класс итераторов. С помощью этого класса мы сможем довольно легко путешествовать по узлам дерева.

В итераторе используется две переменные: указатель на текущее поддерево (на текущий узел) и итератор списка (DListIterator) сыновей поддерева.

template<class T>
class TreeIterator
{
public:
  Tree<T>* tree;
  DListIterator<Tree<T>*> sonsItr;

  TreeIterator () : tree(NULL) {}
  TreeIterator (Tree<T>*);

  void Root (); // перейти  в корневой узел
  void Up (); // перейти  на один уровень вверх
  void Down (); // перейти  на один уровень вниз
  void CreateSon (); // добавить узел  в sons
  void NextSon(); // следующий узел  в sons
  void PreviousSon (); // предыдущий узел  в sons
  void FirstSon (); // первый узел списка sons
  void LastSon (); // последний узел списка sons
  void InsertData (T d); // вставить данные  в текущий узел sons
};

Конструкторы итератора дерева

В итераторе два конструктора. Конструктор без параметров инициазилирует указатель на дерево значением NULL (sonsItr инициализируется в конструкторе DListIterator):

TreeIterator () : tree(NULL) {}
Во второй конструктор передаётся один аргумент - указатель на дерево (или поддерево). В теле конструктора происходит присвоение значений полям итератора:

template<class T>
TreeIterator<T>::TreeIterator (Tree<T>* t)
{
  tree = t; // текущий узел
  sonsItr.node = tree->sons.head; // первый узел списка sons
  sonsItr.list = &tree->sons;
}

Методы класса TreeIterator

Методы класса итератора дерева довольно просты. Во многом благодаря использованию классов DLinkedList и DListIterator.

Прежде всего нам нужно научиться возрващаться к корню из любого узла:

template<class T>
void TreeIterator<T>::Root ()
{
  while (tree->parent != NULL)
    Up();
}

Метод простой. Мы проверяем поле parent текущего узла, пока в нём не окажется NULL. В дереве может быть только один элемент, поле parent которого равно NULL. Так вот, если текущий узел не является корнем, мы переходим на один уровень вверх, используя метод Up.

В методе Up мы проверяем родительский узел текущего узла, и если это не корень, то мы меняем текущий узел и поля sonsItr.

template<class T>
void TreeIterator<T>::Up ()
{
  if (tree->parent != NULL)
  {
    tree = tree->parent;
    sonsItr.node = tree->sons.head;
    sonsItr.list = &tree->sons;
  }
}

Переход на один уровень вниз осуществляется методом Down. Он во многом похож на метод Up, только здесь мы проверяем существование узла на следующем уровне.

template<class T>
void TreeIterator<T>::Down ()
{
  if (sonsItr.node->data != NULL)
  {
    tree = sonsItr.node->data;
    sonsItr.node = tree->sons.head;
    sonsItr.list = &tree->sons;
  }
}

Следующий метод создаёт новый узел в списке sons текущего узла:

template<class T>
void TreeIterator<T>::CreateSon ()
{
  tree->sons.Insert(sonsItr, new Tree<T>);
  sonsItr.node->data->parent = tree;
}

Для вставки нового узла используется метод DLinkedList::Insert. Кроме того, нужно не забыть изменить поле parent нового узла, чтобы он указывал на текущий узел.

Следующие четыре метода почти повторяют функциональность соответствующих методов класса DListIterator.

Перейти к следующему узлу в списке sons:

template<class T>
void TreeIterator<T>::NextSon()
{
  if (sonsItr.node->next != NULL)
  {
    sonsItr.node = sonsItr.node->next;
  }
}

Перейти к предыдущему узлу в списке sons:

template<class T>
void TreeIterator<T>::PreviousSon ()
{
  if (sonsItr.node->previous != NULL)
    sonsItr.node = sonsItr.node->previous;
}

Перейти к первому узлу в списке sons:

template<class T>
void TreeIterator<T>::FirstSon ()
{
  sonsItr.Start();
}

Перейти к последнему узлу в списке sons:

template<class T>
void TreeIterator<T>::LastSon ()
{
  sonsItr.End();
}

Последний метод класса вставляет значение в текущий узел списка sons:

template<class T>
void TreeIterator<T>::InsertData (T d)
{
  if (sonsItr.node->data != NULL)
    sonsItr.node->data->data = d;
}

Заключение

Данные классы не являются полной реализацией деревьев. Нашей целью было создать наиболее простую в использовании и при этом как можно более гибкую реализацию деревьев. Получилось? Смотрите сами:

Tree t;
t.data = 0;

TreeIterator ti (&t);
ti.CreateSon();
ti.InsertData(11);

ti.Down();
ti.CreateSon();
ti.InsertData(21);

ti.Root();
ti.CreateSon();
ti.InsertData(12);

ti.PreviousSon();