Понятие корневого дерева.
В теории графов конечное корневое дерево формально определяется как непустое конечное множество узлов Т, таких что: существует один, специально выделенный узел, называемый корнем, а остальные узлы образуют попарно непересекающиеся подмножества множества узлов Т, каждое из которых является деревом. Это определение позволяет интерпретировать корневое дерево как рекурсивный объект, который содержит сам себя и определяется с помощью себя самого (т. е. дерево определяется в терминах дерева). Определение корневого дерева как определение любого рекурсивного объекта содержит базисную и рекурсивную части. Базисная часть, определяющая корень дерева является нерекурсивным утверждением. Рекурсивная часть определения записана так, чтобы она редуцировалась (сводилась) к базе цепочкой повторных применений. В данном случае дерево с числом узлов n>1 индуктивно определяется через деревья с числом узлов меньше, чем n, пока не достигнут базисный шаг, где дерево состоит из единственного узла - корня. Рекурсивное определение корневого дерева позволяет более простым способом формализовать его структуру и алгоритмы обработки. Для неформального описания корневых деревьев часто используется генеалогическая терминология, согласно которой каждая ветвь отражает отношение потомок-предок между инцидентными ей узлами. Корень дерева- это узел, который не имеет предка. Узлы дерева, которые не имеют потомков называются листьями. Остальные узлы (не листья и не корень) называются разветвлениями. Следующий рисунок иллюстрирует классическое изображение корневого дерева средствами теории графов, где вершины и ребра графа представляют узлы и ветви дерева.
Рис. 1.  Изображение корневого дерева в теории графов .
На этом рисунке заглавные буквы латинского алфавита обозначают узлы, а строчные- ветви корневого дерева. Конфигурация ветвей этого корневого дерева такова, что узел А является корнем, узлы В С и D- разветвлениями, а узлы E, F, G, H, и K - листьями.
Следует отметить, что кроме классического изображения, принятого в теории графов, в области информационных технологий применяются альтернативные способы представления корневых деревьев. На следующем рисунке приведены 3 эквивалентных способа представления исходного корневого дерева: с помощью вложенных скобок (а), уступчатого списка (б) и десятичной системы Дьюи (в) соответственно:
Рис. 2.  Альтернативные способы представления корневого дерева
Приведенные альтернативные способы представления корневых деревьев иллюстрируют возможности практического применения иерархических структур.
Например, десятичная система Дьюи применяется в библиографии, а вложенные скобки - для получения полноскобочной записи при грамматическом разборе арифметических выражений.
Важными метрическими характеристиками корневого дерева является степень и уровень узла. Степенью узла корневого дерева считается число поддеревьев, для которых он является корнем. Для рассмотренного примера корневого дерева: корень А имеет степень 3, степени разветвлений B и D - равны 2, а степень разветвления С равна 1. Степени остальных узлов равны 0, потому что они являются листьями, т. е. не имеют поддеревьев. Уровень узла корневого дерева определяется длиной пути, образованного чередующейся последовательностью узлов и ветвей, который соединяет его с корнем. Длина пути измеряется числом узлов в нем. Для рассмотренного примера корень А имеет уровень 1, разветвления B, C и D имеют уровень 2, а листья E, F, G, H и K - уровень 3.
При измерении длины пути числом ветвей в нем, указанные уровни узлов надо уменьшить на 1.
Обобщением понятия корневого дерева является понятие леса. Под лесом понимается упорядоченное множество непересекающихся корневых деревьев. Отражением близости этих понятий является простота преобразований дерева в лес и наоборот, леса в дерево. Исключение корня превращает дерево в лес.
Наоборот, добавление одного узла превращает лес в дерево, где этот узел становится корнем. Чтобы подчеркнуть близость этих понятий, в некоторых работах для обозначения леса из N деревьев употребляют термин: дерево с N -кратным корнем.

Понятие бинарного дерева.
Важной разновидностью корневых деревьев является класс бинарных деревьев, где каждый узел может иметь не более 2-х потомков. В рекурсивном варианте определения бинарное дерево состоит из корня и 2-х бинарных поддеревьев: левого и правого, причем любое из них может быть пустым. Следующий рисунок иллюстрирует изображение бинарного дерева из 8-ми узлов A, B, C, D, E, F, G, H средствами теории графов.
Рис. 3.   Изображение бинарного дерева в теории графов.
Несмотря на иерархическую структуру, бинарные деревья не являются подмножеством множества деревьев. Например на следующем рисунке показаны 2 различных бинарных дерева, которые эквивалентны как корневые деревья.
Рис. 4.  Отличие корневых и бинарных деревьев
Эти бинарные деревья различны по структуре, потому что корень первого из них имеет только левый потомок, а корень второго - только правый. Однако, как деревья они эквивалентны дереву из 2-х узлов А и В, которое изображено на том же рисунке справа. В общем случае различие между корневым деревом и бинарным деревом состоит в том, что каждый узел корневого дерева может иметь произвольное число поддеревьев, в то время как любой узел бинарного дерева может иметь только 0, 1 или 2 поддерева и существует различие между левыми и правыми поддеревьями.
Несмотря на эти отличия бинарные деревья могут быть использованы для представления корневых деревьев. Возможность такого представления устанавливает следующее естественное соответствие между корневыми и бинарными деревьями. Левая ветвь каждого узла соединяет его с первым узлом следующего уровня, а правая - с другими узлами следующего уровня (братьями). Следующий рисунок демонстрирует естественное соответствие 3-х уровневого корневого дерева его бинарному представлению.
Рис. 5.  Естественное соответствие между корневым и бинарным деревьями.
Естественное соответствие между корневыми и бинарными деревьями имеет важное значение в области информационных технологий, где программирование обработки данных может быть более просто реализовано для бинарных деревьев. Классическим примером иерархической обработки данных являются алгоритмы поиска по бинарному дереву и прохождения бинарного дерева в различном порядке.
Динамическая реализация бинарных деревьев.
Для программной реализации бинарных деревьев чаще всего используют динамические структуры данных, в которых каждый узел управляется записью из 2-х адресных и требуемого числа информационных полей. Адресные поля узла предназначены для хранения адресов левого и правого потомков. При отсутствии левого или правого потомка соответствующим адресным полям узла можно присвоить нулевые значения (NULL). Адресные поля имеют тип указатель на узел бинарного дерева. Информационные поля узлов могут иметь произвольный тип. Они используются для хранения данных и ключей в узлах бинарного дерева. Диаграмма логической структуры узла бинарного дерева представлена на следующем рисунке.
Рис. 6.  Логическая структура узла бинарного дерева
При создании нового узла бинарного дерева в динамической реализации, из кучи распределяется область памяти, объем которой необходим для хранения всех полей его логической структуры. Адрес области памяти, выделенной для нового узла, сохраняется в соответствующем (левом или правом) адресном поле предка.
Динамическое распределение узлов по адресным полям предков позволяет конструировать бинарные деревья с желаемой иерархической структурой информационных полей.
Например, на следующем рисунке приведена логическая структура динамической реализации семантического дерева грамматического разбора арифметического выражения: 7+6*4 .
Рис. 7.  Логическая структура бинарного дерева
Базовый класс бинарных деревьев.
Для объектно-ориентированной программной обработки бинарных деревьев целесообразно сконструировать базовый класс BiNode с защищенными компонентными данными и общедоступными компонентными методами. Компонентные данные класса BiNode следует использовать для формального описания узлов абстрактного бинарного дерева, в котором узлы имеют только адресные поля для связи с другими узлами, но не имеют каких-либо информационных полей.
Общедоступная часть класса BiNode должна включать инвариантные компонентные методы прохождения и поиска по бинарным деревьям, которые не зависят от информационной природы узлов.
Класс BiNode не должен быть предназначен для самостоятельного применения, т. к. узлы дерева без информационных полей не имеют смысла, потому что нельзя никак идентифицировать, что они найдены или пройдены. По этой причине, класс BiNode следует рассматривать как абстрактный класс, который не может быть реализован в объектах. Его следует применять только как базовый класс, который своими адресными полями обеспечивает поддержку иерархической структуры бинарного дерева производных узлов с любыми информационными полями и предоставляет инвариантные базовые методы древовидной обработки данных.
В терминах системы программирования С++ логическая структура декларации базового класса BiNode должна иметь следующий формат:

Пример 1
  class BiNode 
  { 
  protected:  /*спецификация компонентных данных*/ 
  public:     /*спецификация компонентных методов*/ 
  }; 

В защищенной (protected) части декларации класса BiNode рекомендуется специфицировать адресную пару компонентных данных:

Пример 2
  BiNode * left;  /*адрес левого потомка*/ 
  BiNode * right; /*адрес правого потомка*/ 

Для хранения адресов потомков каждого узла бинарного дерева или нулевых (NULL) указателей, при отсутствии соответствующих потомков. Для инициализации этих адресов нулевыми значениями в классе BiNode рекомендуется предусмотреть и явно описать собственный конструктор без аргументов, который удобно специфицировать как inline-подстановку непосредственно в декларации класса.
В общедоступную (public) часть объявления класса BiNode нужно включить декларацию универсальных базовых компонентных методов, которые программно реализуют алгоритмы прохождения (preorder, inorder и postorder) и поиска по бинарному дереву (search). Эти компонентные методы должны предусматривать инвариантный доступ к узлам бинарных деревьев из объектов различных производных классов, который не зависит от специфики обработки их информационных полей.
Компонентный метод search предназначается для реализации алгоритма поиска по бинарному дереву в соответствии с заданным ключом, который следует передавать ему как аргумент. Компонентный метод search должен возвращать адрес узла бинарного дерева, который соответствует ключу, или нулевой указатель (NULL), если объект с заданным ключом не был обнаружен при поиске.
По этой причине естественным типом кода возврата компонентного метода search является указатель на базовый класс (BiNode*). Передача ключа поиска должна быть организована по адресу. С этой целью у компонентного метода search следует предусмотреть аргумент типа (void*). Выбор такого типа аргумента обеспечит его независимость от типа данных ключа поиска, потому что по указателю типа (void*) можно передать адрес данных любого типа, например, адрес строки символов (char*), если требуется организовать поиск по символическому ключу.
С учетом обозначенных предпочтений по типу аргумента и кода возврата, компонентный метод search может быть декларирован в объявлении класса BiNode следующим образом:
Пример 3

  class BiNode 
  { 
  ................... 
  BiNode* search (void*); 
  }; 
Основными элементами спецификации компонентного метода search должны быть: организация направленного перебора существующих узлов бинарного дерева для идентификации по заданному ключу поиска и вставка нового узла, когда ключевой образец поиска не обнаружен. Обеспечивая внешнюю независимость компонентного метода search от типа данных ключа ( с помощью аргумента типа void*), необходимо также выбрать для него инвариантную внутреннюю структуру, которая не зависит от специфики идентификации ключа и вставки нового узла при поиске по бинарному дереву построенному из объектов любого производного класса. Желаемая инвариантность метода search может быть достигнута путем декларации в базовом классе BiNode виртуальных интерфейсов identify и insert, реализация которых планируется в производных классах. Базовый класс только объявляет виртуальные интерфейсы, устанавливая договоренность по типу аргумента и коду возврата.
Приведенное описание виртуальных интерфейсов базового класса, которые необходимы для реализации инвариантного поиска по бинарному дереву, отражает следующая декларация чистых виртуальных функций в классе BiNode:
Пример 4
  class BiNode 
  { 
  ................... 
  virtual int identify (void*) = 0; 
  virtual BiNode* insert (void*) = 0; 
  ................... 
  }; 

При обращении к чистой виртуальной функции базового класса выбирается подходящая реализация из производного класса, соответствующего по типу объекту, который инициирует ее вызов. В частности, вызовы компонентного метода search через указатели на объекты различных производных классов будут порождать вызовы различных производных реализаций чистых виртуальных функций identify и insert при обращении к ним через неявно передаваемый указатель this, который при такой схеме обращения сохраняет адрес объекта производного класса. Обращение к чистым виртуальным функциям через адрес объекта базового класса не имеет смысла из-за отсутствия их реализации в нем.
Производный класс бинарных деревьев.
Чтобы учесть специфику иерархической обработки для унификации и систематизации символьных строк в программе, целесообразно сформировать класс StrNode, производный от базового класса бинарных деревьев BiNode. Объекты класса StrNode должны описывать иерархию бинарного дерева, узлы которого предназначены для хранения текстовых строк. Производный класс StrNode должен наследовать компоненты базового класса и содержать собственные частные (private) компоненты-данные и общедоступные (public) компонентные методы, учитывающие особенности иерархической обработки символьных строк. В соответствии с правилами реализации принципа наследования в системе программирования С++, декларацию класса StrNode можно специфицировать следующим образом:
Пример 5

  class StrNode : public BiNode 
  { 
  private : /*спецификация собственных компонент-данных*/ 
  public  : /*спецификация собственных компонентных методов*/ 
  }; 

Категория наследования public выбрана для того, чтобы сохранить в производном классе привилегии доступа к компонентам, установленные в базовом классе.
Пример 6
class BiNode
{
protected:
    BiNode *left;
    BiNode *right;
public:
    BiNode() { left = right = NULL; }

    void inorder  (...);
    void preorder (...);
    void postorder(...);

    BiNode* search(void*);

    virtual int identify(void*)=0;
    virtual BiNode* insert(void*)=0;
};


class StrNode : public BiNode
{
    char *str;
   ...
public:
    StrNode(const char *s);

    ~StrNode()
    {
        cerr<<"String:\""<<str<<"\" is deleted."<<endl;
        delete []str; 
    }

    virtual int identify(void* s) 
    {
        return strcmp(str,(char*)s); 
    }

    virtual BiNode* insert(void* s)
    {
        return(new StrNode((char*)s));
    }

    StrNode* search(void* s) 
    {
       ...
    }

....

};