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


Пример 9.4


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

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




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



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