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


Пример 9.4 - часть 2


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




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



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