Для объектно-ориентированной программной обработки
бинарных деревьев целесообразно сконструировать базовый класс BiNode с защищенными компонентными данными и общедоступными компонентными
методами. Компонентные данные класса BiNode следует использовать для формального описания
узлов абстрактного бинарного дерева, в котором узлы имеют только адресные поля для связи с другими узлами, но не имеют каких-либо информационных полей.
Общедоступная часть класса BiNode должна включать инвариантные компонентные методы прохождения и поиска по бинарным деревьям, которые не зависят от информационной природы узлов.
Класс BiNode не должен быть предназначен для самостоятельного применения, т. к. узлы дерева без информационных полей не имеют смысла, потому что нельзя никак идентифицировать, что они найдены или пройдены. По этой причине, класс BiNode следует рассматривать как абстрактный класс, который не может быть реализован в объектах. Его следует применять только как базовый класс, который своими адресными полями обеспечивает поддержку иерархической структуры бинарного дерева производных узлов с любыми информационными полями и предоставляет инвариантные базовые методы древовидной обработки данных.
В терминах системы программирования С++ логическая структура декларации базового класса BiNode должна иметь следующий формат:
class BiNode
{
protected: /*спецификация компонентных данных*/
public: /*спецификация компонентных методов*/
};
В защищенной (protected) части декларации класса BiNode рекомендуется специфицировать адресную пару компонентных данных:
BiNode * left; /*адрес левого потомка*/
BiNode * right; /*адрес правого потомка*/
Для хранения адресов потомков каждого узла бинарного дерева или нулевых (NULL) указателей, при отсутствии соответствующих потомков. Для инициализации этих адресов нулевыми значениями в классе BiNode рекомендуется предусмотреть и явно описать собственный конструктор без аргументов, который удобно специфицировать как inline-подстановку непосредственно в декларации класса.
В общедоступную (public) часть объявления класса BiNode нужно включить декларацию универсальных базовых компонентных методов, которые программно реализуют
алгоритмы прохождения (preorder,inorder и postorder) и поиска по бинарному дереву (search). Эти компонентные методы должны предусматривать инвариантный доступ к узлам бинарных деревьев из объектов различных производных классов, который не зависит от специфики обработки их информационных полей.
Компонентные методы preorder, inorder и postorder должны обеспечивать программную реализацию рекурсивных процедур прохождения бинарного дерева, соответственно в прямом, симметричном и концевом порядке. Их спецификация не должна зависеть то способов обработки данных при посещении узла. Например, обход бинарного дерева может проводится в следующих различных целях: отображение информационных полей узлов в заданном порядке, определение метрических характеристик бинарного дерева (уровни и степени узлов), представление бинарного дерева в желаемом формате (уступчатый список, вложенные скобки, десятичная система Дьюи), очистка памяти,
динамически распределенной под узлы бинарного дерева. Перечисленные методы функциональной обработки при обходе узлов бинарного дерева могут быть реализованы в различных производных классах базового класса BiNode, для которых они актуальны. Универсальный интерфейс с различными методами функциональной обработки производных классов в инвариантных методах прохождения бинарного дерева может обеспечить косвенная
адресация компонент, основанная на обращении к методу по его адресу в структуре его класса. По этой причине аргументы компонентных методов прохождения бинарного дерева должны обеспечивать передачу указателя на компонентный метод любого производного класса, обеспечивающий требуемую функциональную обработку при обходе. Поскольку имена производных классов при проектировании базового класса неизвестны, то указатели на методы функциональной обработки из них следует объявить как указатели на компонентные методы базового класса BiNode. По ним можно передавать указатели на компонентные методы производных классов при соответствующем явном преобразовании типов аргументов. Если ограничиться косвенной адресацией компонентных методов, которые не имеют возврата и аргументов (void), то для удобства спецификации аргументов методов прохождения бинарного дерева целесообразно ввести специальный тип VISIT, который должен определяться директивой typedef перед объявлением класса BiNode следующим образом:
class BiNode; /*декларация имени класса*/
typedef void (BiNode::*VISIT) (void);
class BiNode { /*спецификация класса*/ };
Директива typedef в данном случае определяет новый тип VISIT как указатель на компонентный метод класса BiNode (BiNode::*), у которого нет аргументов (void) и отсутствует код возврата (левый void в спецификации typedef). С учетом типа VISIT описание прототипа, например, компонентного метода inorder имеет следующий простой формат в декларации базового класса Binode:
class BiNode {
.............
void inorder (VISIT): /*traversal by infix order*/
.............
};
Для вызова компонентного метода по его адресу в структуре класса, система программирования С++ предоставляет
операторы разыменования (->*) или (.*) в зависимости от способа определения объекта класса (по указателю или по ссылке). При наличии типа VISIT вызов по адресу требуемого метода информационной обработки узлов для обхода бинарного дерева, например, в выше декларированном методе inorder, специфицируется с помощью оператора разыменования (->*) следующим образом:
void BiNode
{
...............
(this ->* V) ();
...............
}
Декларация и спецификация 2-х других компонентных методов прохождения бинарного дерева (preorder и postorder) может быть дана аналогично.
Компонентный метод search предназначается для реализации алгоритма поиска по бинарному дереву в соответствии с заданным ключом, который следует передавать ему как аргумент. Компонентный метод search должен возвращать адрес узла бинарного дерева, который соответствует ключу, или нулевой указатель (NULL), если объект с заданным ключом не был обнаружен при поиске.
По этой причине естественным типом кода возврата компонентного метода search является указатель на базовый класс (BiNode*). Передача ключа поиска должна быть организована по адресу. С этой целью у компонентного метода search следует предусмотреть аргумент типа (void*). Выбор такого типа аргумента обеспечит его независимость от типа данных ключа поиска, потому что по указателю типа (void*) можно передать адрес данных любого типа, например, адрес строки символов (char*), если требуется организовать поиск по символическому ключу.
С учетом обозначенных предпочтений по типу аргумента и кода возврата, компонентный метод search может быть декларирован в объявлении класса BiNode следующим образом:
class BiNode
{
...................
BiNode* search (void*);
};
Основными элементами спецификации компонентного метода search должны быть: организация направленного перебора существующих узлов бинарного дерева для идентификации по заданному ключу поиска и вставка нового узла, когда ключевой образец поиска не обнаружен. Обеспечивая внешнюю независимость компонентного метода search от типа данных ключа ( с помощью аргумента типа void*), необходимо также выбрать для него инвариантную внутреннюю структуру, которая не зависит от специфики идентификации ключа и вставки нового узла при поиске по бинарному дереву построенному из объектов любого производного класса. Желаемая инвариантность метода search может быть достигнута путем декларации в базовом классе BiNode виртуальных интерфейсов identify и insert, реализация которых планируется в производных классах. Базовый класс только объявляет виртуальные интерфейсы, устанавливая договоренность по типу аргумента и коду возврата.
В системе программирования С++ виртуальные интерфейсы декларируются как чистые (PURE) виртуальные функции, которые определяются в базовом классе как компонентные методы без исполняемого кода (имеют нулевой код). Не имея кода, чистые виртуальные функции не обладают реализацией в базовом классе. Чтобы приобрести код они перегружаются одноименными компонентными методами производных классов с соответствующими по типу аргументами и кодом возврата, получая специфичную реализацию в каждом производном классе. Несмотря на различие реализации в каждом производном классе, чистые виртуальные функции обладают идентичным интерфейсом, который установлен и декларирован базовым классом. Таким образом, упомянутые выше виртуальные интерфейсы identify и insert, декларируются в базовом классе BiNode соответствующими чистыми виртуальными функциями, которые определяются в производных классах.
Чистая виртуальная функция identify должна применяться в компонентном методе search, чтобы обозначить необходимость идентификации узлов бинарного дерева по заданному ключу поиска, который был передан методу search через аргумент типа (void*). Она должна обеспечивать целочисленный (int) код возврата и принимать ключевые данные по адресу через свой единственный аргумент, который должен иметь тип (void*) по соображениям, указанным выше. Код возврата используется для анализа результата сравнения заданного ключа поиска с ключевым информационным полем текущего узла бинарного дерева, для идентификации которого была вызвана виртуальная функция identify. Анализ результата идентификации ключа по текущему узлу следует использовать либо для завершения поиска, либо для его продолжения в левом или правом поддереве текущего узла в зависимости от знака кода возврата виртуальной функции identify. Рекомендуется принять следующую договоренность по знаку кода возврата при оценке результатов идентификации узла: нулевой код возврата означает соответствие текущего узла заданному ключу поиска, ненулевой - отсутствие соответствия, причем поиск следует продолжать в правом поддереве текущего узла, если код возврата больше нуля, либо в левом, когда код возврата виртуальной функции identify меньше нуля. Способ сравнения ключей определяется типом ключевых данных и реализуется особенным образом в каждом производном классе в соответствии с установленным интерфейсом базового класса BiNode.
Вторая чистая виртуальная функция insert, декларированная в базовом классе BiNode, используется в компонентном методе search, чтобы обозначить необходимость вставки нового узла в бинарное дерево, если в нем отсутствует узел, который соответствует ключу поиска. Она должна возвращать адрес нового узла бинарного дерева, принимая адрес ключа поиска, переданный в компонентный метод search через аргумент типа (void*). Это означает, что по типу кода возврата и типу аргумента виртуальная функция insert аналогична компонентному методу search, где она должна вызываться. Полученный от виртуальной функции insert адрес нового узла, который создается в ней, следует присвоить свободному адресному полю (left или right) идентифицированного узла в соответствии с текущим знаком ненулевого кода возврата виртуальной функции identify. Очевидно, что виртуальная функция insert может быть вызвана для идентифицированных узлов со степенью меньше чем 2 и только тогда, когда результат сравнения ключей требует продолжить поиск для поддерева, корнем которого должен являться отсутствующий потомок данного узла. Особенности реализации нового узла бинарного дерева специфичны для каждого производного класса, т. к. зависят от структуры его информационных полей, и должны быть конкретизированы в производном классе. Эти особенности не являются существенными для базового компонентного метода search, кроме того, что вставка нового узла должна происходить в соответствии с интерфейсом базового класса.
Приведенное описание виртуальных интерфейсов базового класса, которые необходимы для реализации инвариантного поиска по бинарному дереву, отражает следующая декларация чистых виртуальных функций в классе BiNode:
class BiNode
{
...................
virtual int identify (void*) = 0;
virtual BiNode* insert (void*) = 0;
...................
};
При обращении к чистой виртуальной функции базового класса выбирается подходящая реализация из производного класса, соответствующего по типу объекту, который инициирует ее вызов. В частности, вызовы компонентного метода search через указатели на объекты различных производных классов будут порождать вызовы различных производных реализаций чистых виртуальных функций identify и insert при обращении к ним через неявно передаваемый указатель this, который при такой схеме обращения сохраняет адрес объекта производного класса. Обращение к чистым виртуальным функциям через адрес объекта базового класса не имеет смысла из-за отсутствия их реализации в нем.
Следует отметить , что в соответствии с терминологией системы программирования С++ класс BiNode является абстрактным классом. По правилам системы программирования С++ абстрактным называется класс, который содержит хотя бы 1 чистую виртуальную функцию (Базовый класс BiNode объявляет сразу 2 чистые виртуальные функции.). Абстрактный класс не может быть реализован в объекте, но указатели или ссылки на него вполне допустимы. Производные классы, где перегружены унаследованные от базового класса чистые виртуальные функции, абстрактными не являются и, следовательно, могут быть реализованы в объектах. Существует мнение, что абстрактные классы особенно полезны для программирования иерархических структур. В данном случае абстрактный класс BiNode определяет универсальную структуру и методы обработки бинарных деревьев, узлы которых могут быть реализованы объектами любых производных классов.
