АСП1/К2 2016

Zadaci

1. zadatak

Postavka

Na slici je dato jedno nekompletno prikazano binarno stablo (desno. Ukoliko preorder obilazak takvog stabla daje poredak čvorova ACBDFE, nacrtati sve moguće izglede ovog stabla.

   A
 /   \
C     ...
 \
  B

Rešenje

Pogledajmo najpre obilazak A CB DFE

Levi deo je kompletan i D mora biti koren desnog podstabla. Odatle dolaze kombinacije:

   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. zadatak

Postavka

Napisati u pseudokodu funkciju koja u binarnom stablu na čiji koren pokazuje pokazivač root utvrđuje da li postoji čvor čija pozicija u stablu (u odnosu na koren) je simetrična u odnosu na poziciju čvora na koji pokazuje pokazivač node. Smatrati da svaki čvor binarnog stabla pored informacionog sadržaja sadrži pokazivače na levo i desno podstablo i pokazivač na roditeljski čvor.

Rešenje

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

Rešenje se sastoji od toga da se vratimo unazad, pamteći put, i onda silazimo opet ali obrnutim putem. Ukoliko se isprazni stek, to znači da postoji simetrični član.