2020-04-07
93
Для объектно-ориентированной программной обработки бинарных деревьев целесообразно сконструировать базовый класс 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, который при такой схеме обращения сохраняет адрес объекта производного класса. Обращение к чистым виртуальным функциям через адрес объекта базового класса не имеет смысла из-за отсутствия их реализации в нем.
