АСП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 ulančana lista (koja glumi stek), to znači da postoji simetrični član.

CHECK_SYMMETRIC(root, node)
path = nil
while node ≠ root do
    step = GETNODE
    parent = parent(node)
    if left(parent) = node then
        info(step) = 0
    else
        info(step) = 1
    end_if
    node = parent
    next(step) = path
    path = step
end_while
while node ≠ nil do
    if path = nil then
        return true
    end_if
    if info(path) = 0 then
        node = right(node)
    else
        node = left(node)
    end_if
    step = path
    path = next(path)
    FREE(step)
end_while
return false