Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

PostOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);

PostOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);

aProcessNode(aRoot);

end;

end;

Обратите внимание на то, как каждая рекурсивная процедура проверяет, не является ли переданный ей узел нулевым. В этом случае она не выполняет никаких действий, немедленно осуществляя выход. Следовательно, со временем рекурсивный вызов процедур завершится (поскольку дерево простирается не до бесконечности).

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

будет выполняться в ходе последовательности рекурсивных вызовов. Дело в том, что рекурсивные процедуры хранят свое состояние в стеке программы, размер которого в общем случае ограничен. Если выясняется, что рекурсивная процедура может иметь слишком много уровней, следует подумать над тем, как избавиться от рекурсии за счет применения внешнего стека. Используя внешний стек вместо стека программы, можно быть уверенным, что при необходимости размер стека в куче можно будет увеличить (пока выделенный объем кучи не будет исчерпан, однако, в общем случае этот объем значительно превышает размер стека программы).

Мы используем стек, созданный на основе связного списка класса TtdStack, который был описан в главе 3. Для выполнения обхода в ширину мы заталкиваем в стек корневой узел и выполняем цикл, который продолжается до тех пор, пока стек не опустеет. Мы выталкиваем из стека верхний узел и посещаем его. Если правая дочерняя связь этого узла является ненулевой, мы заталкиваем ее в стек. Затем заталкиваем в стек левую дочернюю связь узла, если она является ненулевой. (Заталкивание дочерних узлов в указанном порядке означает, что вначале из стека выталкивается левый дочерний узел.) Если стек не является пустым, цикл повторяется. Обход завершается немедленно после опустошения стека.

Листинг 8.5. Нерекурсивный обход в ширину

type

TtdVisitProc = procedure ( aData : pointer;

aExtraData : pointer;

var aStopVisits : boolean );

function TtdBinaryTree.btNoRecPreOrder(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;

{выполнить с ним указанное действие; если в результате возвращаемое значение переменной StopNow равно true, вернуть этот узел}

aAction(Node^.btData, aExtraData, StopNow);

if StopNow then begin

Result := Node;

Stack.Clear;

end

{в противном случае продолжить цикл}

else begin

{затолкнуть правую дочернюю связь, если она не нулевая}

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;

Касательно

кода, приведенного в листинге 8.5, следует сделать несколько замечаний. Во-первых, мы используем процедуру действия, которая несколько сложнее применявшейся ранее. Процедура типа TtdVisitProc предоставляет пользователю метода обхода большую степень управления процессом, а именно -возможность остановить обход. Т.е. пользователь класса бинарного дерева может выполнять действия как для каждой записи (посещая все узлы), так и для первой найденной записи (т.е. для поиска первого узла, удовлетворяющего заданному условию). Значение третьего параметра процедуры действия, aStopVisits, устанавливается равным false вызывающей процедурой, а если процедуре действия нужно остановить обход, это значение может быть установлено равным true (в этом случае метод обхода вернет элемент, который привел к возврату значения true процедурой действия).

Однако, важная особенность приведенного в листинге 8.5 кода состоит в том, что процедура считает дерево не пустым. Фактически эта процедура - внутренняя процедура класса бинарного дерева, возможного при определенных условиях, и она будет вызываться только для дерева, которое содержит, по меньшей мере, один узел.

Убедившись, насколько просто избавиться от рекурсии при обходе в ширину, можно было бы предположить, что это легко сделать и для остальных двух видов обхода. Однако, применяя это же подход к симметричному обходу и обходу в глубину, мы сталкиваемся с препятствием. Чтобы понять, о чем идет речь, рассмотрим исключение рекурсии для симметричного обхода тем же способом, который был применен для обхода в ширину. Теоретически в цикле нужно было бы затолкнуть в стек правый дочерний узел, затем сам узел, а затем левый дочерний узел. Далее, со временем, нужно было бы вытолкнуть узел из стека и выполнить его обработку. Но, вытолкнув узел из стека, как узнать, встречался ли он ранее? Если узел ранее встречался, его нужно посетить;

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

В действительности нужно сделать следующие действия. Вытолкнуть узел из стека. Если ранее узел не встречался, нужно затолкнуть в стек правый дочерний узел, пометить узел как "встречавшийся", затолкнуть его, а затем затолкнуть в стек левый дочерний узел. Если ранее узел встречался (помните, что он уже помечен?), следует просто его обработать. Но как пометить узел? В конце концов, узел - это указатель, и в действительности не хотелось бы с ним возиться. Я предлагаю следующее решение: после заталкивания в стек "встречавшегося" узла нужно затолкнуть узел nil. В этом случае выталкивание из стека нулевого узла свидетельствует о том, что следующий узел в стеке является тем, который должен быть обработан.

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