II Olimpiada Informatyczna 1994/95
|
Zadanie: DRZ
|
Autor: Wojciech Rytter
|
Zawody I stopnia |
Plik źródłowy: | DRZ.??? (np. pas, c, cpp) |
Plik wykonywalny: | DRZ.exe |
Plik wejściowy: | DRZ.in |
Plik wyjściowy: | DRZ.out |
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ł w (oprócz korzenia) ma swojego (dokładnie jednego) ojca v. Jeśli węzeł v jest ojcem w, to w jest synem v. Węzły nie mające synów nazywamy liśćmi. Synów węzła w, ich synów, synów ich synów itd. nazywamy potomkami węzła w. Każdy węzeł - oprócz korzenia - jest potomkiem korzenia. Każdy węzeł ma swój poziom. Korzeń ma poziom 0, 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.
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 0 (zero), zaś dla j > 1, j-ty wyraz ciągu jest numerem ojca węzła
j.
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: (lp), gdzie l i p oznaczają napisy
przyporządkowane odpowiednio lewemu i prawemu synowi w. 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 |
Twój program powinien utworzyć następujący plik DRZ.OUT:
0 1 2 2 1 5 6 6 5
((()())((()())()))
Dla pliku DRZ.IN:
4
1 2 2 3
Twój program powinien utworzyć plik DRZ.OUT:
NIE
Twój program powinien szukać pliku DRZ.IN w katalogu bieżącym i tworzyć plik DRZ.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę DRZ.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku DRZ.EXE.