Drzewa
Limit pamięci: 32 MB
Drzewa występują bardzo często w informatyce. W odróżnieniu od drzew w naturze
drzewa w informatyce rosną do góry nogami: korzeń jest na górze, a liście są
na dole. Drzewo składa się z elementów zwanych węzłami. Jeden z węzłów jest
korzeniem. Każdy węzeł (oprócz korzenia) ma swojego (dokładnie
jednego) ojca . Jeśli węzeł jest ojcem , to
jest synem . Węzły nie mające synów nazywamy liśćmi.
Synów węzła , ich synów, synów ich synów itd. nazywamy potomkami
węzła . Każdy węzeł - oprócz korzenia - jest potomkiem korzenia.
Każdy węzeł ma swój poziom. Korzeń ma poziom , a synowie mają poziom
o jeden większy od swoich ojców.
Drzewo jest pełnym drzewem binarnym wtedy i tylko wtedy, gdy każdy węzeł ma
dokładnie dwóch lub zero synów. W drzewach binarnych rozróżniamy lewego i
prawego syna.
Powyższy rysunek przedstawia przykładowe pełne drzewo binarne. Węzły tego drzewa
są ponumerowane w specjalnej kolejności (nazywanej w literaturze angielskiej
preorder). W kolejności tej korzeń ma numer , ojciec poprzedza
synów, a lewy syn i dowolny jego potomek ma numer mniejszy niż prawy syn i każdy
jego potomek.
Jest wiele sposobów zapisu pełnych drzew binarnych z taką numeracją węzłów. Oto
trzy z nich.
Zapis genealogiczny
Jest to ciąg liczb. Pierwszy element ciągu jest równy (zero),
zaś dla , -ty wyraz ciągu jest numerem ojca węzła
.
Zapis nawiasowy
Każdemu węzłowi przyporządkowujemy napis złożony z nawiasów. Liściom
przyporządkowujemy napis . Każdemu z pozostałych węzłów w
przyporządkowujemy napis postaci: , gdzie i
oznaczają napisy przyporządkowane odpowiednio lewemu i prawemu
synowi . Napis przyporządkowany korzeniowi jest zapisem nawiasowym
drzewa.
Zapis poziomowy
Jest to ciąg poziomów kolejnych liści drzewa (zgodnie z przyjętą
numeracją).
Drzewo przedstawione na rysunku można opisać następująco:
Zapis genealogiczny | 0 1 2 2 4 4 1 7 7 |
Zapis nawiasowy | ((()(()()))(()())) |
Zapis poziomowy | 2 3 3 2 2 |
Zadanie
Napisz program, który wczytuje ze standardowego wejścia ciąg liczb i bada, czy
jest on zapisem poziomowym pełnego drzewa binarnego. Jeśli nie jest, to zapisuje
w standardowym wyjściu jeden wyraz NIE, a jeśli jest, to znajduje dwa
inne zapisy tego drzewa (genealogiczny i nawiasowy) i zapisuje je w
standardowym wyjściu.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest dodatnia liczba wyrazów
ciągu (nie większa niż 2500). W drugim wierszu zapisane są kolejne wyrazy ciągu
oddzielone pojedynczymi odstępami. Liczby w standardowym wejściu są zapisane
poprawnie. Twój program nie musi tego sprawdzać.
Wyjście
Standardowe wyjście powinno zawierać:
- tylko jeden wyraz NIE
- albo:
- w pierwszym wierszu kolejne wyrazy zapisu genealogicznego oddzielone
pojedynczymi odstępami,
- w drugim wierszu zapis nawiasowy, tzn. ciąg nawiasów lewych i prawych bez
odstępów między nimi.
Przykłady
Dla danych wejściowych:
5
2 2 3 3 2
poprawną odpowiedzią jest:
0 1 2 2 1 5 6 6 5
((()())((()())()))
Dla danych wejściowych:
4
1 2 2 3
poprawną odpowiedzią jest:
NIE
Autor zadania: Wojciech Rytter.