АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
Алгоритм создания бинарного дерева (псевдокод)
Для построения дерева необходимо создать в памяти ЭВМ элемент следующего типа:
P, Q - рабочие указатели
V=maketree(key,rec) - процедура, которая создает сегмент ключа и записи
P=getnode - генерация нового элемента
r=rec
k=key
V=P
left=nil
right=nil
tree - указатель на корень дерева
Введем сначала первое значение ключа, потом процедурой maketree сгенерируем сам элемент узла дерева. Далее идем по циклу до тех пор, пока указатель не передвинется на нулевое значение.
read (key, rec)
tree = maketree(key, rec)
while not eof do
p = tree
q = tree
read (key, rec)
v = maketree(key, rec)
while p <> nil do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if p=nil then writeln (‘Это корень’)
tree=v
else
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endif
endwhile
return
Если по этому алгоритму строить упорядоченное бинарное дерево, то при поступлении ключей в последовательности 14, 18, 6, 21, 1, 13, 15 получим дерево, изображенное на рисунке ниже.
Для того, чтобы просмотреть элементы созданного дерева, необходимо выполнить его обход.
Алгоритм "обхода" дерева
Пусть задано бинарное дерево:
Существуют три вида обхода бинарных деревьев. Рассмотрим их на примере заданного дерева:
1) Обход сверху вниз (корень посещается ранее, чем поддеревья): A, B, C;
2) Слева направо: B, A, C;
3) Снизу вверх (корень посещается после поддеревьев): B, C, A.
Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.
Рекурсивные процедуры обхода дерева:
1) PROCEDURE pretrave (tree)
IF tree<>nil
THEN PRINT info (tree)
tree=left (pretrave (tree))
tree=right (pretrave (tree))
END IF
RETURN
2) PROCEDURE intrave (tree)
IF tree<>nil
THEN tree=left (intrave (tree))
PRINT info (tree)
tree=right (intrave (tree))
END IF
RETURN
3) PROCEDURE postrave (tree)
IF tree<>nil
THEN tree=left (postrave (tree))
tree=right (postrave (tree))
PRINT info (tree)
END IF
RETURN