Поскольку ссылки занимают место указателей на дочерние узлы дерева, нужно как‑то различать ссылки и обычные указатели на потомков. Проще всего добавить к узлам новые переменные 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
Перед тем, как удалить узел из дерева, необходимо вначале удалить всех его потомков. После этого легко удалить уже сам узел.
Предположим, что удаляемый узел является левым потомком своего родителя. Его указатель на левого потомка является ссылкой, указывающей на предыдущий узел в дереве. После удаления узла, его предшественник становится предшественником родителя удаленного узла. Чтобы удалить узел, просто заменяем указатель на левого потомка его родителя на указатель на левого потомка удаляемого узла.
Указатель на правого потомка удаляемого узла является ссылкой, которая указывает на следующий узел в дереве. Так как удаляемый узел является левым потомком своего родителя, и поскольку у него нет потомков, эта ссылка указывает на родителя, поэтому ее можно просто опустить. На рис. 6.24 показано дерево с рис. 6.23 после удаления узла F. Аналогично удаляется правый потомок.
Private Sub RemoveLeftChild(parent As ThreadedNode)
Dim target As ThreadedNode
Set target = parent.LeftChild
Set parent.LeftChild = target.LeftChild
End Sub
@Рис. 6.24. Удаление узла F из дерева со ссылками
=========145
Квадродеревья (quadtrees) описывают пространственные отношения между элементами на площади. Например, это может быть карта, а элементы могут представлять собой положение домов или предприятий на ней.
Каждый узел квадродерева представляет собой участок на площади, представленной квадродеревом. Каждый узел, кроме листьев, имеет четыре потомка, которые представляют четыре квадранта. Листья могут хранить свои элементы в коллекциях связных списков. Следующий код показывает секцию Declarations для класса QtreeNode.
' Потомки.
Public NWchild As QtreeNode
Public NEchild As QtreeNode
Public SWchild As QtreeNode
Public SEchild As QtreeNode
' Элементы узла, если это не лист.
Public Items As New Collection
Элементы, записанные в квадродереве, могут содержать пространственные данные любого типа. Они могут содержать информацию о положении, которую дерево может использовать для поиска элементов. Переменные в простом классе QtreeItem, который представляет элементы, состоящие из точек на местности, определяются так:
Public X As Single
Public Y As Single
Чтобы построить квадродерево, вначале поместим все элементы в корневой узел. Затем определим, содержит ли этот узел достаточно много элементов, чтобы его стоило разделить на несколько узлов. Если это так, создадим четыре потомка узла и распределим элементы между четырьмя потомками в соответствии с их положением в четырех квадрантах исходной области. Затем рекурсивно проверяем, не нужно ли разбить на несколько узлов дочерние узлы. Продолжим разбиение до тех пор, пока все листья не будут содержать не больше некоторого заданного числа элементов.
На рис. 6.25 показано несколько элементов данных, расположенных в виде квадродерева. Каждая область разбивается до тех пор, пока она не будет содержать не более двух элементов.
Квадродеревья удобно применять для поиска близлежащих объектов. Предположим, имеется программа, которая рисует карту с большим числом населенных пунктов. После того, как пользователь щелкнет мышью по карте, программа должна найти ближайший к выбранной точке населенный пункт. Программа может перебрать весь список населенных пунктов, проверяя для каждого его расстояние от заданной точки. Если в списке N элементов, то сложность этого алгоритма порядка O(N).
====146
@Рис. 6.25. Квадродерево