Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Однако, важная особенность приведенного в листинге 8.5 кода состоит в том, что процедура считает дерево не пустым. Фактически эта процедура - внутренняя процедура класса бинарного дерева, возможного при определенных условиях, и она будет вызываться только для дерева, которое содержит, по меньшей мере, один узел.
Убедившись, насколько просто избавиться от рекурсии при обходе в ширину, можно было бы предположить, что это легко сделать и для остальных двух видов обхода. Однако, применяя это же подход к симметричному обходу и обходу в глубину, мы сталкиваемся с препятствием. Чтобы понять, о чем идет речь, рассмотрим исключение рекурсии для симметричного обхода тем же способом, который был применен для
если нет, его вместе с дочерними узлами необходимо затолкнуть в стек, но в правильном порядке.
В действительности нужно сделать следующие действия. Вытолкнуть узел из стека. Если ранее узел не встречался, нужно затолкнуть в стек правый дочерний узел, пометить узел как "встречавшийся", затолкнуть его, а затем затолкнуть в стек левый дочерний узел. Если ранее узел встречался (помните, что он уже помечен?), следует просто его обработать. Но как пометить узел? В конце концов, узел - это указатель, и в действительности не хотелось бы с ним возиться. Я предлагаю следующее решение: после заталкивания в стек "встречавшегося" узла нужно затолкнуть узел nil. В этом случае выталкивание из стека нулевого узла свидетельствует о том, что следующий узел в стеке является тем, который должен быть обработан.
Нерекурсивный алгоритм симметричного обхода работает следующим образом. Затолкните в стек корневой узел и войдите в цикл, который должен выполняться до момента опустошения стека. Вытолкните верхний узел из стека. Если он является нулевым, вытолкните из стека следующий узел и посетите его. Если вытолкнутый узел не является нулевым, затолкните в стек правый дочерний узел (если он является ненулевым), затем сам узел, затем затолкните нулевой указатель и в заключение затолкните в стек левый дочерний узел (если он является ненулевым). Снова выполните цикл.
Как и в случае обхода в ширину, метод предполагает, что дерево является не пустым, и что в нем присутствует, по меньшей мере, один узел. В данном случае это еще более важно, поскольку метод может работать совершенно не правильно, если нулевой узел заталкивается в стек, который не связан с алгоритмом.
Листинг 8.6. Нерекурсивный симметричный обход
function TtdBinaryTree.btNoRecInOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не опустеет}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается запрос на прекращение обхода, вернуть этот узел}
if (Node = nil) then begin
Node := Stack.Pop;
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result := Node;
Stack.Clear;
end;
end
{в противном случае дочерние узлы этого узла в стек еще не заталкивались}
else begin
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть
узел, а за ним - нулевой указатель}Stack.Push(Node);
Stack.Push(nil);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.BtChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
end;
Нерекурсивный алгоритм обхода в глубину работает аналогично. Необходимо затолкнуть в стек корневой узел и войти в цикл, который будет выполняться до момента опустошения стека. В цикле необходимо вытолкнуть из стека верхний узел. Если он является нулевым, нужно вытолкнуть из стека следующий узел и выполнить его обработку. Если узел не является нулевым, следует затолкнуть в стек сам узел, затем нулевой указатель, затем правый дочерний узел (если он является ненулевым), а затем левый дочерний узел (если он является ненулевым). Затем необходимо снова выполнить цикл.
Листинг 8.7. Нерекурсивный обход в глубину
function TtdBinaryTree.btNoRecPostOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не опустеет}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается значение false (т.е. обход должен быть прекращен), вернуть этот узел}
if (Node = nil) then begin
Node := Stack.Pop;
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result := Node;
Stack.Clear;
end;
end
{в противном случае дочерние узлы этого узла в стек еще не заталкивались}
else begin
{затолкнуть узел, а за ним - нулевой указатель}
Stack.Push(Node);
Stack.Push(nil);
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.btChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
end;
Как и ранее, по тем же причинам, метод предполагает, что дерево является не пустым.
Обход по уровням
Мы еще не рассматривали обход по уровням, при котором вначале посещается корневой узел, затем слева направо посещаются два возможных узла на первом уровне, затем слева направо четыре возможных узла на втором уровне и т.д. Этот метод обхода кажется слишком сложным для кодирования, но в действительности он очень прост. Достаточно знать один прием. Он заключается в следующем применении очереди. Поместим корневой узел в очередь, и будем выполнять цикл до тех пор, пока очередь не опустеет. Удалим из очереди верхний узел. Посетим его. Если его левая дочерняя связь является ненулевой, поместим ее в очередь. Если правая дочерняя связь является ненулевой, поместим в очередь и ее. Если очередь не пуста, снова выполним цикл. Вот, собственно, и все.