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


Класс BinTree - часть 3


End Sub

Public Sub ReplaceAndDelete(q As TreeNode) 'Заменяет узел на самый правый If Not (root.right.root Is Nothing) Then root.right.ReplaceAndDelete q Else 'Найден самый правый q.key = root.key: q.info = root.info Set root = root.left.root End If

End Sub

Пример 9.4.

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

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


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