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


Класс 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() 'Инфиксный обход дерева (левое поддерево, корень, правое)




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



Книжный магазин