Класс TreeNode

Как следует из определения бинарного дерева, каждый его узел содержит ссылки на левого и правого сына. Кроме того, предполагается, что информация, хранящаяся в узле, сопровождается ключом. Несколько упрощая ситуацию, можно предложить следующее описание класса TreeNode, задающее описание узла бинарного дерева поиска:

'Class TreeNode

'Элемент дерева

Public key As String

Public info As String

Public left As New BinTree

Public right As New BinTree

Класс BinTree

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

Option Explicit

'Класс BinTree

'Бинарным будем называть дерево, у которого каждая вершина имеет

'одного или двух потомков, называемых левым и правым сыном (поддеревом).

'В дальнейшем будем полагать, что узел нашего дерева содержит

'информационное поле info и поле ключа - key.

'Деревом поиска (двоичным или лексикографическим деревом) будем называть

'бинарное дерево, в котором ключ каждой вершины больше ключа, хранящегося

'в корне левого поддерева, и меньше ключа, хранящегося в корне правого поддерева.

'Рассмотрим операции над деревом поиска: поиск, включение, удаление элементов

'и обход дерева. Все операции сохраняют структуру дерева поиска.

Public root As TreeNode

Public Sub PrefixOrder()

'Префиксный обход дерева (корень, левое поддерево, правое)

If Not (root Is Nothing) Then

With root

Debug.Print "key: ",.key, "info: ",.info

.left.PrefixOrder

.right.PrefixOrder

End With

End If

End Sub

Public Sub InfixOrder()

'Инфиксный обход дерева (левое поддерево, корень, правое)

If Not (root Is Nothing) Then

With root

.left.InfixOrder

Debug.Print "key: ",.key, "info: ",.info

.right.InfixOrder

End With

End If

End Sub

Public Sub PostfixOrder()

'Постфиксный обход дерева (левое поддерево, правое, корень)

If Not (root Is Nothing) Then

With root

.left.PostfixOrder

.right.PostfixOrder

Debug.Print "key: ",.key, "info: ",.info

End With

End If

End Sub

Public Sub SearchAndInsert(key As String, info As String)

'Если в дереве есть узел с ключом key,

'то возвращается информация в этом узле - работает поиск

'Если такого узла нет, то создается новый узел и его поля

'заполняются информацией, - работает вставка.

'Вначале поиск

If root Is Nothing Then ' элемент не найден и происходит вставка

Set root = New TreeNode

root.key = key: root.info = info

ElseIf key < root.key Then

'Поиск в левом поддереве

root.left.SearchAndInsert key, info

ElseIf key > root.key Then

'Поиск в правом поддереве

root.right.SearchAndInsert key, info

Else 'Элемент найден - возвращается результат поиска

info = root.info

End If

End Sub

Public Sub DelInTree(key As String)

'Эта процедура позволяет удалить элемент дерева с заданным ключом

'Удаление с сохранением структуры дерева более сложная операция,

'чем вставка или поиск. Причина сложности в том, что при удалении

'элемента остаются два его потомка, которые необходимо корректно

'связать с оставшимися элементами, чтобы не нарушить структуру дерева поиска.

'В программе анализируются три случая:

'Удаляется лист дерева (нет потомков - нет проблем),

'Удаляется узел с одним потомком (потомок замещает удаленный узел),

'Есть два потомка. В этом случае узел может быть заменен одним из двух

'возможных кандидатов, не имеющих двух потомков.

'Кандидатами являются самый левый узел правого подддерева и

'самый правый узел левого поддерева.

'Мы производим удаление в левом поддереве.

Dim q As TreeNode

If root Is Nothing Then

Debug.Print "Key is not found"

ElseIf key < root.key Then

'Удаляем из левого поддерева

root.left.DelInTree key

ElseIf key > root.key Then

'Удаляем из правого поддерева

root.right.DelInTree key

Else

'Удаление узла

Set q = root

If q.right.root Is Nothing Then

Set root = q.left.root

ElseIf q.left.root Is Nothing Then

Set root = q.right.root

Else 'есть два потомка

q.left.ReplaceAndDelete q

End If

Set q = Nothing

End If

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. (html, txt)

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

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

2. Для простоты в методе SearchAndInsert мы совместили две операции поиска элемента по заданному ключу и вставки нового элемента. Если в дереве найден элемент с заданным ключом, то предполагается, что речь идет о поиске и возвращается информация из информационного поля этого элемента. Если в дереве нет элемента с таким ключом, то создается новый узел дерева. Заметьте, что наше решение не позволяет производить замену элемента, а в процессе поиска не уведомляет об отсутствии элемента с заданным ключом

3. Удаление элемента из дерева поиска осложняется тем, что нужно поддерживать структуру дерева поиска. В тех случаях, когда нужно удалить элемент, у которого есть два потомка, вызывается специальная процедура ReplaceAndDelete. Эта процедура ищет кандидата, который мог бы заменить удаляемый элемент, сохраняя структуру дерева.

4. Недостатком деревьев поиска является то, что они могут быть плохо сбалансированы и могут иметь относительно длинные ветви. Так, если при создании дерева поиска, ключи будут поступать в отсортированном порядке, то дерево будет представлено одной ветвью. Работа с этой структурой данных предполагает, что при создании и добавлении элементов в дерево ключи поступают в случайном порядке, хорошо перемешанные. Эта структура особенно применима в тех случаях, когда в процессе работы над данными широко используются все операции - поиск, вставка и удаление.

5. Мы не стали писать реализацию этого класса, оперирующего с данными, хранящимися в списках Excel или базе данных Access, поскольку это выходит за рамки этой лекции.