АСП1/К2 2016
1. задатак
Поставка
На слици је дато једно некомплетно приказано бинарно стабло (десно. Уколико преордер обилазак таквог стабла даје поредак чворова АЦБДФЕ, нацртати све могуће изгледе овог стабла.
A / \ C ... \ B
Решење
Погледајмо најпре обилазак А ЦБ ДФЕ
Леви део је комплетан и D мора бити корен десног подстабла. Одатле долазе комбинације:
A A A A A
/ \ / \ / \ / \ / \
C D C D C D C D C D
\ / \ \ / \ / \ \ \ \
B F E B F B F B F B F
/ \ \ /
E E E E
2. задатак
Поставка
Написати у псеудокоду функцију која у бинарном стаблу на чији коренпоказује показивач роотутврђује да ли постоји чвор чија позиција у стаблу (у односу на корен) је симетрична у односу на позицијучворана који показује показивач ноде. Сматрати да сваки чвор бинарног стабла поред информационог садржаја садржи показиваче на лево и десноподстабло и показивач на родитељски чвор.
Решење
CHECK_SYMMETRIC(root,node)
S = INIT_STACK()
while node ≠ root do
parent = parent(node)
if left(parent) = node then
STACK_PUSH(S,0)
else
STACK_PUSH(S,1)
end_if
node = parent
end_while
while node ≠ nil
if STACK_EMPTY(S) then
return true
end_if
if STACK_POP(S) = 0 then
node = right(node)
else
node = left(node)
end_if
end_while
return false
Решење се састоји од тога да се вратимо уназад, памтећи пут, и онда силазимо опет али обрнутим путем. Уколико се испразни стек, то значи да постоји симетрични члан.