Упорядоченные деревья

Двоичные деревья часто являются естественным способом представления и обработки данных в компьютерных программах. Поскольку многие компьютерные операции являются двоичными, они естественно преобразуются в операции с двоичными деревьями. Например, можно преобразовать двоичное отношение «меньше» в двоичное дерево. Если использовать внутренние узлы дерева для обозначения того, что «левый потомок меньше правого» вы можете использовать двоичное дерево для записи упорядоченного списка. На рис. 6.15 показано двоичное дерево, содержащее упорядоченный список с числами 1, 2, 4, 6, 7, 9.

@Рис. 6.14. Пример обратного обхода дерева в программе Trav2

======133

@Рис. 6.15. Упорядоченный список: 1, 2, 4, 6, 7, 9.

Добавление элементов

Алгоритм вставки нового элемента в дерево такого типа достаточно прост. Начнем с корневого узла. По очереди сравним значения всех узлов со значением нового элемента. Если значение нового элемента меньше или равно значению узла, перейдем вниз по левой ветви дерева. Если новое значение больше, чем значение узла, перейдем вниз по правой ветви. Когда этот процесс дойдет до листа, элемент помещается в эту точку.

Чтобы поместить значение 8 в дерево, показанное на рис. 6.15, мы начинаем с корня, который имеет значение 4. Поскольку 8 больше, чем 4, переходим по правой ветви к узлу 9. Поскольку 8 меньше 9, переходим затем по левой ветви к узлу 7. Поскольку 8 больше 7, снова пытаемся пойти по правой ветви, но у этого узла нет правого потомка. Поэтому новый элемент вставляется в этой точке, и получается дерево, показанное на рис. 6.16.

Следующий код добавляет новое значение ниже узла в упорядоченном дереве. Программа начинает вставку с корня, вызывая процедуру InsertItem Root, new_value.

Private Sub InsertItem(node As SortNode, new_value As Integer)

Dim child As SortNode

If node Is Nothing Then

' Мы дошли до листа.

' Вставить элемент здесь.

Set node = New SortNode

node.Value = new_value

MaxBox = MaxBox + 1

Load NodeLabel(MaxBox)

Set node.Box = NodeLabel(MaxBox)

With NodeLabel(MaxBox)

.Caption = Format$(new_value)

.Visible = True

End With

ElseIf new_value <= node.Value Then

' Перейти по левой ветви.

Set child = node.LeftChild

InsertItem child, new_value

Set node.LeftChild = child

Else

' Перейти по правой ветви.

Set child = node.RightChild

InsertItem child, new_value

Set node.RightChild = child

End If

End Sub

Когда эта процедура достигает конца дерева, происходит нечто совсем неочевидное. В Visual Basic, когда вы передаете параметр подпрограмме, этот параметр передается по ссылке, если вы не используете зарезервированное слово ByVal. Это означает, что подпрограмма работает с той же копией параметра, которую использует вызывающая процедура. Если подпрограмма изменяет значение параметра, значение в вызывающей процедуре также изменяется.

Когда процедура InsertItem рекурсивно вызывает сама себя, она передает указатель на дочерний узел в дереве. Например, в следующих операторах процедура передает указатель на правого потомка узла в качестве параметра узла процедуры InsertItem. Если вызываемая процедура изменяет значение параметра узла, указатель на потомка также автоматически обновляется в вызывающей процедуре. Затем в последней строке кода значение правого потомка устанавливается равным новому значению, так что созданный новый узел добавляется к дереву.

Set child = node.RightChild

Insertltem child, new_value

Set node.RightChild = child