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

Решење се састоји од тога да се вратимо уназад, памтећи пут, и онда силазимо опет али обрнутим путем. Уколико се испразни стек, то значи да постоји симетрични члан.