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

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.

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