Основы офисного программирования и язык VBA


Класс BinTree


Класс BinTree содержит одно свойство - объект класса TreeNode, задающий корень дерева и группу операций над элементами дерева. Одним из основных методов класса является метод SearchAndInsert, который, по существу, реализует две операции - поиска элемента в дереве по заданному ключу и вставки элемента в дерево. Заметьте, что вставка должна быть реализована так, чтобы выполнялось основное условие дерева поиска: для каждой вершины ее ключ больше всех ключей вершин левого поддерева и меньше всех ключей вершин правого поддерева. Такая структура обеспечивает эффективное выполнение операций поиска, так как в этом случае для поиска требуется просмотр вершин, лежащих только на одной ветви дерева, ведущей от корня к искомому элементу. Этот метод обеспечивает создание класса, позволяя, начав с корня, вставлять элемент за элементом. Кроме этого метода мы определим методы для удаления элементов и группу методов обхода дерева. Все методы реализованы с использованием рекурсивных алгоритмов. Приведем описание класса:

Пример 9.4.

(html, txt)

Все методы класса довольно подробно прокомментированы, однако хотелось бы подчеркнуть некоторые моменты:

  1. Начнем с общего замечания, связанного с реализацией рекурсивных алгоритмов. Рекурсия это мощный инструмент, полезный при решении многих задач по обработке данных. Для тех, кто не привык писать рекурсивные программы, мы рекомендуем внимательно разобрать реализацию приведенных методов класса. Каждое рекурсивное определение содержит некоторый базис, позволяющий найти решение в простейшем случае без использования рекурсии, а затем вся задача сводится к нескольким подобным задачам, но меньшей размерности. Если число задач, к которым сводится исходная задача, не меньше двух, то можно заведомо говорить, что рекурсивное решение намного проще не рекурсивного алгоритма и использование рекурсии оправданно. Для пояснения этих общих утверждений обратимся к примеру. В нашем классе приведены три метода обхода бинарного дерева: PrefixOrder, InfixOrder, PostfixOrder.


    Начало  Назад  Вперед