Структуры и алгоритмы обработки данных. Ключарев А.А - 61 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

61
большие накладные расходы при изменении структуры дерева (напри-
мер, при обмене местами двух поддеревьев).
1.3.4.5. Основные операции
Реализация операций будет рассматриваться для двоичных деревьев,
представленных как динамическая структура.
В качестве основных операций с двоичными деревьями рассмотрим
операцию прямого обхода двоичного дерева в рекурсивной и нерекур-
сивной форме. Реализация обратного и симметричного обходов анало-
гична. Операции добавления, поиска и удаления вершин дерева зави-
сят от принятого порядка вершин, поэтому будут представлены в 2.3.4.1,
посвященном упорядоченным деревьям.
procedure PreOrder_BinTree(Node: PTree);
{Рекурсивный обход двоичного дерева в прямом порядке}
begin
writeln(Node^.Data);
if Node^.Left <> nil then PreOrder_BinTree(Node^.Left);
if Node^.Right <> nil then PreOrder_BinTree(Node^.Right);
end;
В процедуре, реализующей нерекурсивный обход двоичного дерева,
используется стек, хранящий путь от корня дерева до предка текущей
вершины. Описание этого стека и операции с ним аналогичны тем, что
приведены в 1.2.9 с одним уточнением – элементы стека хранят указа-
тели на вершины дерева.
Процедура работает в двух режимах. В первом режиме осуществля-
ется обход по направлению к левым потомкам до тех пор, пока не встре-
тится лист, при этом выполняется печать значений вершин, и занесе-
ние указателей на них в стек. Во втором режиме осуществляется воз-
врат по пройденному пути с поочередным извлечением указателей из
стека до тех пор, пока не встретится вершина, имеющая еще не напеча-
танного правого потомка. Тогда процедура переходит в первый режим
и исследует новый путь, начиная с этого потомка:
procedure NR_PreOrder_BinTree(Tree: PTree);
{Нерекурсивный обход двоичного дерева в прямом порядке}
var
Node: Ptree; {Указатель на текущую вершину}
S: ^TypeElement; {Стек указателей вершин}

Страницы