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


         

одного или двух потомков, называемых


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
'Поиск в правом поддереве

Содержание  Назад  Вперед