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


         

Эта процедура позволяет удалить элемент


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

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