АСП1/К2 2019

Zadaci

1. zadatak

Postavka

Neka je skoro kompletno ili kompletno binarno stablo predstavljeno sekvencijalnom memorijskom reprezentacijom (nizom). Na osnovu prosleđenog niza u kome su smeštene celobrojne vrednosti koje predstavljaju informacioni sadržaj čvorova, formirati ekvivalentno binarno stablo ulančane reprezentacije.

Rešenje

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