Нерекурсивный алгоритм обхода дерева в прямом порядке

Пусть T – указатель на бинарное дерево; А – стек, в который заносятся адреса еще не пройденных вершин; TOP – вершина стека; P – рабочая переменная.

1. Начальная установка: TOP:=0; P:=T.

2. Если P=nil, то перейти на 4. {конец ветви}

3. Вывести P^.info. Вершину заносим в стек: TOP:=TOP+1; A[TOP]:=P; шаг по левой ветви: P:=P^.llink; перейти на 2.

4. Если TOP=0, то КОНЕЦ.

5. Достаем вершину из стека: P:=A[TOP]; TOP:=TOP-1;
Шаг по правой связи: P:=P^.rlink; перейти на 2.

Реализация нерекурсивного алгоритма поиска может выглядеть следующим образом:

Function Locate(x: integer; T: Link):Link; var found: boolean; begin found:= false; while (T <> nil) and not found do if T^.elem = x then found:= true
else if T^.elem > x then T:=T^. left else T:=T^.right; Locate:= T end;

Для упрощения процедуры поиска можно использовать дерево с узлом-барьером (последний пустой узел z, в который засылается элемент для поиска x)

function Locate(x: integer; T: Link):Link; begin z^.elem:=x; while T^.elem <> x do if T^.elem > x then T:=T^. left else T:=T^.right; Locate:= T end;

34. Сортировка методом прямого включения

Элементы мысленно делятся на уже готовую последовательность a1,...,ai-1 и исходную последовательность.

При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

Суть алгоритма такова:

for i = 2 to n

x = a(i)

находим место среди а(1)…а(i) для включения х

next i

Есть два алгоритма сортировки методом прямого включения. Первый - без барьера

Алгоритм сортировки методом прямого включения без барьера

for i = 2 to n

x = a(i)

for j = i - 1 downto 1

if x < a(j)

then a(j + 1) = a(j)

else go to L

endif

next j

L: a(j + 1) = x

next i

return

Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while, то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.

Алгоритм сортировки методом прямого включения с барьером

for i = 2 to n

x = a(i)

a(0) = x {a(0) - барьер}

j = i - 1

while x < a(j) do

a(j +1) = a(j)

j = j - 1

endwhile

a(j +1) = x

next i

return