АСП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 do
    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