позволяет упростить вывод элементов в различном порядке. Вы можете использовать тот же
прием, чтобы облегчить обращение к узлам дерева в произвольном порядке. На-
пример, если поместить ссылки в листья двоичного дерева, то выполнение сим-
метричного и обратного обходов упростится. Если дерево упорядоченное, то это
обход в прямом и обратном порядке сортировки.
При создании ссылок указатели на предшественников узла (симметричный
порядок) и потомков должны помещаться в неиспользованных указателях дочер-
них узлов. Если узел имеет неиспользованный левый указатель на потомка, сохра-
ните ссылку в позиции, указывающей на предшественника узла при симметрич-
ном обходе. Если узел имеет неиспользованный правый указатель на потомка,
сохраните ссылку в позиции, указывающей на дочерний узел при симметричном
обходе. Поскольку ссылки симметричны и ссылки левых потомков указывают на
предыдущих правых, а правых - на следующие узлы, этот тип деревьев называет-
ся деревом с симметричными ссылками (symmetrically threaded tree). На рис. 6.22
показано подобное дерево (потоки выделены пунктирными линиями).
Рис. 6.22. Дерево с симметричными ссылками
Поскольку ссылки занимают позиции указателей на дочерние узлы, необхо-
димо найти какое-то различие между ссылками и обычными указателями на до-
черние узлы. Проще всего это сделать, добавив в узлы новые поля, такие как Boolean
- HasLef tChi Id и HasRightChild, указывающие, есть ли у узла правые
и левые потомки.
Чтобы использовать ссылки для нахождения предшественника узла, необхо-
димо проверить левый указатель на дочерний узел. Если указатель - ссылка, то он
указывает на предшественника узла. Если указатель имеет значение nil, то этот
узел является первым в дереве, поэтому не имеет предшественника. В обратном
случае двигайтесь по направлению этого левого указателя. Затем следуйте за пра-
вым указателем потомка, пока не достигнете узла, в котором вместо правого по-
томка имеется ссылка. Этот узел (а не тот, на который указывает ссылка) - пред-
шественник первоначального узла. Он, в свою очередь, является самым правым
в левой от исходного узла ветви дерева. Следующий код показывает, как можно
найти предшественника узла в Delphi.
function Predecessor(node : PThreadedNode) : PThreadedNode;
var
child : PThreadedNode;
begin
if (nodeA.LeftChild=nil) then
// Это первый узел при симметричном обходе.
Predecessor := nil
else if (node^.HasLeftChild) then begin
// Это указатель на узел.
// Нахождение крайнего правого узла слева.
child := node^.LeftChild;
while (child^.HasRightChild) do
child := child^.RightChild;
Predecessor := child;
end else
// Ссылка указывает на предшественника.
Predecessor := node^ .LeftChild;
end;
Аналогично выполняется поиск следующего узла. Если правый указатель на
дочерний узел - ссылка, то он указывает на потомка узла. Если указатель имеет
значение nil, этот узел - последний в дереве, поэтому он не имеет потомка. В об-
ратном случае следуйте за указателем на правый дочерний узел. Затем двигайтесь
за указателями на левый дочерний узел до тех пор, пока не достигнете узла со
ссылкой для указатель левого дочернего узла. Тогда найденный узел окажется сле-
дующим за исходным. Это будет самый левый узел в правой от исходного узла
ветви дерева.
Удобно также ввести функции, определяющие положение первого и последне-
го узлов дерева. Чтобы найти первый узел, просто следуйте за левыми указателя-
ми на дочерние узлы вниз от корня, пока не достигнете узла с нулевым указате-
лем. Чтобы найти последний узел, следуйте за правыми указателями на дочерние
узлы вниз от корня, пока не достигнете узла с нулевым указателем.
function FirstNode : PThreadedNode;
begin
Result := Root;
While (Result^.LeftChildonil) do
Result := Result^.LeftChild;
end;
function LastNode : PThreadedNode;
begin
Result := Root;
While (Result^.Right Childonil) do
Result:=Result^.RightChild;
end;
Используя эти функции, можно легко записать процедуры, которые отобра-
жают узлы дерева в прямом и обратном порядках.
procedure Inorder;
var
node : PThreadedNode;
begin
// Нахождение первого узла.
node := FirstNode;
// Обход списка.
while (nodeonil) do
begin
VisitNode(nodeA.Value);
node := Successor(node);
end;
end;
procedure Reverselnorder;
var
node : PThreadedNode;
begin
// Нахождение последнего узла.
node := LastNode;
// Обход списка.
while (nodeonil) do
begin
VisitNode(Node^.Value);
node := Predecessor(node);
end;
Процедура вывода узлов в порядке симметричного обхода, описанная ранее,
использует рекурсию. Устранить рекурсию вы можете с помощью этих новых про-
цедур, которые не используют ни рекурсию, ни системный стек.
Каждый указатель на потомка в дереве содержит либо связь с дочерним узлом,
либо поток для предшественника или потомка. Так как каждый узел имеет два ука-
зателя на дочерние узлы, то если в дереве всего N узлов, оно будет содержать 2 * N
связей и потоков. Приведенные алгоритмы обхода посещают каждую связь и поток
в дереве один раз, поэтому для их выполнения требуется О(2 * N) = O(N) шагов.
Эти процедуры можно немного ускорить, если отследить индексы первого и пос-
леднего узлов дерева. Тогда не нужно будет искать первый или последний узел пе-
ред выводом узлов по порядку. Поскольку эти алгоритмы обращаются ко всем N
узлам в дереве, время выполнения для алгоритмов также будет порядка O(N), но
на практике они работают немного быстрее. |
Главная
Каталог файлов
