АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета
Функция поиска по бинарному дереву
Переменной search будет присваиваться указатель на найденное звено:
p = tree
whlie p <> nil do
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
search = nil
return
Алгоритм поиска по бинарному дереву с включением (вставкой).
p = tree
q = nil
while p <> nil do
q = p
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
v = maketree(key, rec)
if q = nil then
tree = v
else
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endif
search = v
return
Вспомогательный указатель q здесь отстает на один шаг от рабочего p.
Алгоритм поиска по бинарному дереву с исключением (удалением).
Данный алгоритм разработан для поиска по дереву с удалением для всех трех возможных случаев нахождения узлов, причем в случае наличия у удаляемого узла двух сыновей его место занимает преемник (на рисунке узел 13 занимает место удаляемого узла 12).
Введем указатели:
p - рабочий указатель;
q - отстает от р на один шаг;
v - указывает на преемника удаляемого узла;
t - отстает от v на один шаг;
s - на один шаг впереди v (указывает на левого сына или пустое место).
В результате поиска преемника на узел 13 должен указывать указатель v, а указатель s - на пустое место (как показано на рисунке).
q = nil
p = tree
while (p <> nil) and (k(p) <> key) do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if p = nil then ‘Ключ не найден’
return
endif
if left(p) = nil then v = right(p)
else if right(p) = nil
then v = left(p)
else
‘У nod(p) - два сына’
‘Введем два указателя (t отстает от v на 1 шаг, s - опережает)’
t = p
v = right(p)
s = left(v)
while s <> nil do
t = v
v = s
s = left(v)
endwhile
if t <> p then
‘v не является сыном p’
left(t) = right(v)
right(v) = right(p)
endif
left(v) = left(p)
endif
endif
if q = nil then ‘p - корень’
tree = v
else if p = left(q)
then left(q) = v
else right(q) = v
endif
endif
freenode(p)
return