VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

:

Private Sub Preorder(node As Integer)

Print NodeLabel (node) ' Узел.

' Первый потомок.

If node * 2 + 1 0

node = queue.Item(1)

queue.Remove 1

' Обращение к узлу.

Print NodeLabel(node)

' Поместить в очередь потомков узла.

For Each child In node.Children

queue.Add child

Next child

Loop

End Sub

=====132

Программа Trav2 демонстрирует обход деревьев, использующих коллекции

дочерних узлов. Программа является объединением программ Nary, которая

оперирует деревьями порядка N, и программы Trav1, которая демонстрирует

обходы деревьев.

Выберите узел, и нажмите на кнопку Add Child (Добавить дочерний узел),

чтобы добавить к узлу потомка. Нажмите на кнопки Preorder, Inorder,

Postorder или Breadth First, чтобы увидеть примеры соответствующих обходов.

На рис. 6.14 показана программа Trav2, которая отображает обратный обход.

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

Двоичные деревья часто являются естественным способом представления и

обработки данных в компьютерных программах. Поскольку многие компьютерные

операции являются двоичными, они естественно преобразуются в операции с

двоичными деревьями. Например, можно преобразовать двоичное отношение

«меньше» в двоичное дерево. Если использовать внутренние узлы дерева для

обозначения того, что «левый потомок меньше правого» вы можете использовать

двоичное дерево для записи упорядоченного списка. На рис. 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.RightChild

DeleteItem child, target_value

Set node.RightChild = child

Else

' Искомый узел найден.

Set target = node

If target.LeftChild Is Nothing Then

' Заменить искомый узел его правым потомком.

Set node = node.RightChild

ElseIf target.RightChild Is Nothing Then

' Заменить искомый узел его левым потомком.

Set node = node.LeftChild

Else

' Вызов подпрограмы ReplaceRightmost для замены

' искомого узла самым правым узлом

' в его левой ветви.

Set child = node.LeftChild

ReplaceRightmost node, child

Set node.LeftChild = child

End If

End If

End Sub

Private Sub ReplaceRightmost(target As SortNode, repl As SortNode)

Dim old_repl As SortNode

Dim child As SortNode

If Not (repl.RightChild Is Nothing) Then

' Продолжить движение вправо и вниз.

Set child = repl.RightChild

ReplaceRightmost target, child

Set repl.RightChild = child

Else

' Достигли дна.

' Запомнить заменяющий узел repl.

Set old_repl = repl

' Заменить узел repl его левым потомком.

Set repl = repl.LeftChild

' Заменить искомый узел target with repl.

Set old_repl.LeftChild = target.LeftChild

Set old_repl.RightChild = target.RightChild

Set target = old_repl

End If

End Sub

======137-138

Алгоритм использует в двух местах прием передачи параметров в рекурсивные

подпрограммы по ссылке. Во-первых, подпрограмма DeleteItem использует этот

прием для того, чтобы родитель искомого узла указывал на заменяющий узел.

Следующие операторы показывают, как вызывается подпрограмма DeleteItem:

Set child = node.LeftChild

DeleteItem child, target_value

Set node.LeftChild = child

Когда процедура обнаруживает искомый узел (узел 8 на рис. 6.19), она

получает в качестве параметра узла указатель родителя на искомый узел.

Устанавливая параметр на замещающий узел (узел 7), подпрограмма DeleteItem

задает дочерний узел для родителя так, чтобы он указывал на новый узел.

Следующие операторы показывают, как процедура ReplaceRightMost рекурсивно

вызывает себя:

Set child = repl.RightChild

ReplaceRightmost target, child

Set repl.RightChild = child

Когда процедура находит самый правый узел в левой от удаляемого узла ветви

(узел 7), в параметре repl находится указатель родителя на самый правый

узел. Когда процедура устанавливает значение repl равным repl.LeftChild,

она автоматически соединяет родителя самого правого узла с левым дочерним

узлом самого правого узла (узлом 5).

Программа TreeSort использует эти процедуры для работы с упорядоченными

двоичными деревьями. Введите целое число, и нажмите на кнопку Add, чтобы

добавить элемент к дереву. Введите целое число, и нажмите на кнопку Remove,

чтобы удалить этот элемент из дерева. После удаления узла, дерево

автоматически переупорядочивается для сохранения порядка «меньше».

Обход упорядоченных деревьев

Полезное свойство упорядоченных деревьев состоит в том, что их порядок

совпадает с порядком симметричного обхода. Например, при симметричном

обходе дерева, показанного на рис. 6.20, обращение к узлам происходит в

порядке 2-4-5-6-7-8-9.

@Рис. 6.20. Симметричный обход упорядоченного дерева: 2, 4, 5, 6, 7, 8, 9

=========139

Это свойство симметричного обхода упорядоченных деревьев приводит к

простому алгоритму сортировки:

1. Добавить элемент к упорядоченному дереву.

2. Вывести элементы, используя симметричный обход.

Этот алгоритм обычно работает достаточно хорошо. Тем не менее, если

добавлять элементы к дереву в определенном порядке, то дерево может стать

высоким и тонким. На рис. 6.21 показано упорядоченное дерево, которое

получается при добавлении к нему элементов в порядке 1, 6, 5, 2, 3, 4.

Другие последовательности также могут приводить к появлению высоких и

тонких деревьев.

Чем выше становится упорядоченное дерево, тем больше времени требуется

для добавления новых элементов в нижнюю часть дерева. В наихудшем случае,

после добавления N элементов, дерево будет иметь высоту порядка O(N).

Полное время вставки всех элементов в дерево будет при этом порядка O(N2).

Поскольку для обхода дерева требуется время порядка O(N), полное время

сортировки чисел с использованием дерева будет равно O(N2)+O(N)=O(N2).

Если дерево остается достаточно коротким, оно имеет высоту порядка

O(log(N)). В этом случае для вставки элемента в дерево потребуется всего

порядка O(log(N)) шагов. Вставка всех N элементов в дерево потребует

порядка O(N * log(N)) шагов. Тогда сортировка элементов при помощи дерева

потребует времени порядка O(N * log(N)) + O(N) = O(N * log(N)).

Время выполнения порядка O(N * log(N)) намного меньше, чем O(N2).

Например, построение высокого и тонкого дерева, содержащего 1000 элементов,

потребует выполнения около миллиона шагов. Построение короткого дерева с

высотой порядка O(log(N)) займет всего около 10.000 шагов.

Если элементы первоначально расположены в случайном порядке, форма

дерева будет представлять что-то среднее между этими двумя крайними

случаями. Хотя его высота может оказаться несколько больше, чем log(N),

оно, скорее всего, не будет слишком тонким и высоким, поэтому алгоритм

сортировки будет выполняться достаточно быстро.

@Рис. 6.21. Дерево, полученное добавлением элементов в порядке 1, 6, 5,

2, 3, 4

==========140

В 7 главе описываются способы балансировки деревьев, для того, чтобы они

не становились слишком высокими и тонкими, независимо от того, в каком

порядке в них добавляются новые элементы. Тем не менее, эти методы

достаточно сложны, и их не имеет смысла применять в алгоритме сортировки

при помощи дерева. Многие из алгоритмов сортировки, описанных в 9 главе,

более просты в реализации и обеспечивают при этом лучшую

производительность.

Деревья со ссылками

Во 2 главе показано, как добавление ссылок к связным спискам позволяет

упростить вывод элементов в разном порядке. Вы можете использовать тот же

подход для упрощения обращения к узлам дерева в различном порядке.

Например, помещая ссылки в листья двоичного дерева, вы можете облегчить

выполнение симметричного и обратного обходов. Для упорядоченного дерева,

это обход в прямом и обратном порядке сортировки.

Для создания ссылок, указатели на предыдущий и следующий узлы в порядке

симметричного обхода помещаются в неиспользуемых указателях на дочерние

узлы. Если не используется указатель на левого потомка, то ссылка

записывается на его место, указывая на предыдущий узел при симметричном

обходе. Если не используется указатель на правого потомка, то ссылка

записывается на его место, указывая на следующий узел при симметричном

обходе. Поскольку ссылки симметричны, и ссылки левых потомков указывают на

предыдущие, а правых — на следующие узлы, этот тип деревьев называется

деревом с симметричными ссылками (symmetrically threaded tree). На рис.

6.22 показано дерево с симметричными ссылками, которые обозначены

пунктирными линиями.

Поскольку ссылки занимают место указателей на дочерние узлы дерева, нужно

как-то различать ссылки и обычные указатели на потомков. Проще всего

добавить к узлам новые переменные HasLeftChild и HasRightChild типа

Boolean, которые будут равны True, если узел имеет левого или правого

потомка соответственно.

Чтобы использовать ссылки для поиска предыдущего узла, нужно проверить

указатель на левого потомка узла. Если этот указатель является ссылкой, то

ссылка указывает на предыдущий узел. Если значение указателя равно Nothing,

значит это первый узел дерева, и поэтому он не имеет предшественников. В

противном случае, перейдем по указателю к левому дочернему узлу. Затем

проследуем по указателям на правый дочерний узел потомков, до тех пор, пока

не достигнем узла, в котором на месте указателя на правого потомка

находится ссылка. Этот узел (а не тот, на который указывает ссылка)

является предшественником исходного узла. Этот узел является самым правым в

левой от исходного узла ветви дерева. Следующий код демонстрирует поиск

предшественника:

@Рис. 6.22. Дерево с симметричными ссылками

==========141

Private Function Predecessor(node As ThreadedNode) As ThreadedNode Dim

child As ThreadedNode

If node.LeftChild Is Nothing Then

' Это первый узел в порядке симметричного обхода.

Set Predecessor = Nothing

Else If node.HasLeftChild Then

' Это указатель на узел.

' Найти самый правый узел в левой ветви.

Set child = node.LeftChild

Do While child.HasRightChild

Set child = child.RightChild

Loop

Set Predecessor = child

Else

' Ссылка указывает на предшественника.

Set Predecessor = node.LeftChild

End If

End Function

Аналогично выполняется поиск следующего узла. Если указатель на правый

дочерний узел является ссылкой, то она указывает на следующий узел. Если

указатель имеет значение Nothing, то это последний узел дерева, поэтому он

не имеет последователя. В противном случае, переходим по указателю к

правому потомку узла. Затем перемещаемся по указателям дочерних узлов до

тех, пор, пока очередной указатель на левый дочерний узел не окажется

ссылкой. Тогда найденный узел будет следующим за исходным. Это будет самый

левый узел в правой от исходного узла ветви дерева.

Удобно также ввести функции для нахождения первого и последнего узлов

дерева. Чтобы найти первый узел, просто проследуем по указателям на левого

потомка вниз от корня до тех пор, пока не достигнем узла, значение

указателя на левого потомка для которого равно Nothing. Чтобы найти

последний узел, проследуем по указателям на правого потомка вниз от корня

до тех пор, пока не достигнем узла, значение указателя на правого потомка

для которого равно Nothing.

Private Function FirstNode() As ThreadedNode

Dim node As ThreadedNode

Set node = Root

Do While Not (node.LeftChild Is Nothing)

Set node = node.LeftChild

Loop

Set PirstNode = node

End Function

Private Function LastNode() As ThreadedNode

Dim node As ThreadedNode

Set node = Root

Do While Not (node.RightChild Is Nothing)

Set node = node.RightChild

Loop

Set FirstNode = node

End Function

=========142

При помощи этих функций вы можете легко написать процедуры, которые выводят

узлы дерева в прямом или обратном порядке:

Private Sub Inorder()

Dim node As ThreadedNode

' Найти первый узел.

Set node = FirstNode()

' Вывод списка.

Do While Not (node Is Nothing)

Print node.Value

Set node = Successor(node)

Loop

End Sub

Private Sub PrintReverseInorder()

Dim node As ThreadedNode

' Найти последний узел

Set node = LastNode

' Вывод списка.

Do While Not (node Is Nothing)

Print node. Value

Set node = Predecessor(node)

Loop

End Sub

Процедура вывода узлов в порядке симметричного обхода, приведенная ранее в

этой главе, использует рекурсию. Для устранения рекурсии вы можете

использовать эти новые процедуры, которые не используют ни рекурсию, ни

системный стек.

Каждый указатель на дочерние узлы в дереве содержит или указатель на

потомка, или ссылку на предшественника или последователя. Так как каждый

узел имеет два указателя на дочерние узлы, то, если дерево имеет N узлов,

то оно будет содержать 2 * N ссылок и указателей. Эти алгоритмы обхода

обращаются ко всем ссылкам и указателям дерева один раз, поэтому они

потребуют выполнения O(2 * N) = O(N) шагов.

Можно немного ускорить выполнение этих подпрограмм, если отслеживать

указатели на первый и последний узлы дерева. Тогда вам не понадобится

выполнять поиск первого и последнего узлов перед тем, как вывести список

узлов по порядку. Так как при этом алгоритм обращается ко всем N узлам

дерева, время выполнения этого алгоритма также будет порядка O(N), но на

практике он будет выполняться немного быстрее.

========143

Работа с деревьями со ссылками

Для работы с деревом со ссылками, нужно, чтобы можно было добавлять и

удалять узлы из дерева, сохраняя при этом его структуру.

Предположим, что требуется добавить нового левого потомка узла A. Так как

это место не занято, то на месте указателя на левого потомка узла A

находится ссылка, которая указывает на предшественника узла A. Поскольку

новый узел займет место левого потомка узла A, он станет предшественником

узла A. Узел A будет последователем нового узла. Узел, который был

предшественником узла A до этого, теперь становится предшественником нового

узла. На рис. 6.23 показано дерево с рис. 6.22 после добавления нового узла

X в качестве левого потомка узла H.

Если отслеживать указатель на первый и последний узлы дерева, то требуется

также проверить, не является ли теперь новый узел первым узлом дерева. Если

ссылка на предшественника для нового узла имеет значение Nothing, то это

новый первый узел дерева.

@Рис. 6.23. Добавление узла X к дереву со ссылками

=========144

Учитывая все вышеизложенное, легко написать процедуру, которая добавляет

нового левого потомка к узлу. Вставка правого потомка выполняется

аналогично.

Private Sub AddLeftChild(parent As ThreadedNode, child As ThreadedNode)

' Предшественник родителя становится предшественником нового узла.

Set child. LeftChild = parent.LeftChild

child.HasLeftChild = False

' Вставить узел.

Set parent.LeftChild = child

parent.HasLeftChild = True

' Родитель является последователем нового узла.

Set child.RightChild = parent

child.HasRightChild = False

' Определить, является ли новый узел первым узлом дерева.

If child.LeftChild Is Nothing Then Set FirstNode = child

End Sub

Перед тем, как удалить узел из дерева, необходимо вначале удалить всех его

потомков. После этого легко удалить уже сам узел.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31