Kod Prufera -- odzyskiwanie drzewa

[Tybias]

Cześć,

chcę się nauczyć kodu Prufera, dla przykładu zrobiłem sobie przykładowe drzewo jak na załączonym rysunku:

Kod z tego drzewa wychodzi mi P:(9,9,8,6,6,8,3) , następnie próbuje odzyskać drzewo z tego kodu i tak:

1. Nie ma 1, wiec -> (1,9)
2. Nie ma 2, więc -> (2,9)
3. Nie ma 4, więc -> (4,8)
4. Nie ma 5, więc -> (5,6)
5. Nie ma 7, więc -> (7,6)
6. 8 i 9 są, więc kończę odzyskiwanie.

I w tym momencie zostały mi nie wykorzystane cztery cyfry ze zbioru N: (3,6,8,9), i co się z nimi teraz robi? z rysunku wiem, że muszą być jeszcze pary (9,3)(8,3)(6,8) ale jak to wyciągnąć z kodu?

[placky]

Piszesz sobie dwa ciągi - jeden na górze od 1 do n+2, drugi - kod Prufera - na dole (długości n). Odkodowujesz, biorąc kolejne cyfry kodu od lewej i sprawdzając, która najmniejszy z góry nie występuje na dole. Po połączeniu wykreślasz. Tym sposobem po przed ostatnim kroku (7,6) masz jeszcze 8 i 3 na dole oraz 3, 6, 8, 9 na górze. Działając zgodnie z tym samym algorytmem, łączysz (8,6) i (3,8). Zostaje Ci 9 i 3 na górze - to ostatnie połączenie.