Nəsil ağacı
Katya öz otağının divarına soy ağacını yerləşdirməyə qərar verdi. Soy ağacı sadə bir quruluşa malikdir:
Ağacın kökü Katyanın özüdür.
Katyanın anası və atası var, bu da sol və sağ alt ağacları təşkil edir.
Hər bir insanın anası və atası olduğuna görə, ağacın hər bir düyünündə də sol və sağ alt ağaclar olmalıdır. Lakin Katya bütün ulu nənə və ulu babalarını tanımır, buna görə də bəzi düyünlərdə bir və ya iki alt ağac olmaya bilər.
Katya hər bir düyündə qohumlarının portretlərini asdı, ağacın kökündə isə öz portretini yerləşdirdi. Nəticə çox gözəl oldu!
Katyanın kiçik qardaşı Anton başa düşdü ki, Katyanın soy ağacı onun ağacına da uyğun gəlir, sadəcə kök düyündəki portreti dəyişmək kifayətdir. Bir az düşündükdən sonra qərara gəldi ki, ağacı ümumi etmək olar, sadəcə kök düyündə onun və bacısının ümumi portretini asmaq kifayətdir.
Ağac artıq ümumi olduğuna görə, Anton onun tərtibatına öz töhfəsini vermək istədi. Ən sadə yol - bütün portretləri Antonun öz əlləri ilə hazırladığı çərçivələrə yerləşdirməkdir, çünki uşaq bağçasında ona gözəl çərçivələr hazırlamağı öyrətmişdilər. Anton işə başladı və tezliklə kifayət qədər gözəl rəngarəng çərçivələri oldu. Katya evdə olmayanda, o, planını həyata keçirməyə qərar verdi. Əvvəlcə Anton bütün yarpaqları çıxardı, bu əməliyyata soldan sağa başlayaraq. (Yarpaq - alt ağacları olmayan zirvədir.) Çıxarılan portretləri Anton bir yığına topladı və öz otağına apardı. Sonra Katyanın otağına qayıtdı və proseduru təkrarladı. Nəticədə divarda yalnız Katyanın portreti qaldı. Anton bu portreti də öz otağına apardı.
Bu zaman Anton dəhşətlə başa düşdü ki, əlində qalan portret yığınlarından ağacı bərpa edə bilməyəcək! Katya tezliklə universitetdən gələcək və Anton hiss edir ki, böyük problemləri olacaq. Antonçikə ağacı bərpa etməkdə kömək edin! Sizə Katyanın ağacın bütün düyünlərini işarələdiyi hərf işarələri kömək etməlidir. Hər bir düyün aşağıdakı şərtlərə cavab verir:
Sol alt ağacın bütün düyünlərinin hərfləri əlifba sırasına görə cari düyünün hərf işarəsindən əvvəl gəlir,
Sağ alt ağacın bütün düyünlərinin hərfləri əlifba sırasına görə cari düyünün hərf işarəsindən sonra gəlir.
Şəkildə ağacın nümunəsi və Antonun əməliyyat ardıcıllığı göstərilmişdir.
Giriş verilənləri
Giriş faylı bir neçə sətir ehtiva edir, hər birində çıxarılan düyünlərin hərf işarələrini ehtiva edən bir sətir göstərilir. Sonuncu sətir '*' işarəsini ehtiva edir - məlumat sətirlərinin sonunu göstərir.
Çıxış verilənləri
Çıxış faylında ağacın strukturunu aşağıdakı ardıcıllıqla verin:
Əgər ağac boşdursa, çıxış da boşdur,
Əgər ağac boş deyilsə, məlumatları aşağıdakı ardıcıllıqla verin:
Kök düyünün məlumatları,
Sol alt ağacın məlumatları,
Sağ alt ağacın məlumatları.
Əgər bir neçə həll yolu varsa, istənilən birini verə bilərsiniz.