АСП1/К2 2019

Задаци

1. задатак

Поставка

Нека је скоро комплетно или комплетно бинарно стабло представљено секвенцијалном меморијском репрезентацијом (низом). На основу прослеђеног низа у коме су смештене целобројне вредности које представљају информациони садржај чворова, формирати еквивалентно бинарно стабло уланчане репрезентације.

Решење

FORM TREE(arr, n)
ALLOCATE(nodes[n])
j = 1
nodes[1] = GETNODE(arr[1])
for i = 1 to n do
    nodes[i] = GETNODE(arr[i])
    if j < n then
        j = j + 1
        left(nodes[i]) = GETNODE(arr[j])
    end_if
    if j < n then
        j = j + 1
        right(nodes[i]) = GETNODE(arr[j])
    end_if
end_for
return nodes[1]

GETNODE(value)
ALLOCATE(node)
left(node) = nil
right(node) = nil
value(node) = value
return node