Nəsil ağacı#2242
Katya ailə şəcərəsini otağının divarına asmaq qərarına gəldi. Şəcərə aşağıdakı quruluşa malikdir:
Şəcərənin kökü elə Katyanın özüdür.
Katyanın anası və atası var, bunlar uyğun olaraq sol və sağ altşəcərələrdir.
Şəcərədəki hər bir şəxsin də anası və atası var, yəni istənilən düyünün ideal halda sol və sağ altşəcərəsi olmalıdır. Lakin Katya bütün ulu babalarını və ulu nənələrini tanımır, ona görə də bəzi düyünlərin bir və ya hər iki altşəcərəsi olmaya bilər.
Katya qohumlarının portretlərini hər düyündə asıb, öz portretini kökdə yerləşdirib. Hər şey gözəl alınıb!
Katyanın kiçik qardaşı Anton başa düşdü ki, əgər kökdəki portreti dəyişsə, bu şəcərə onun da ailə şəcərəsi ola bilər. Bir qədər düşündükdən sonra, o qərara gəldi ki, kökdə həm özünün, həm də Katyanın birgə portretini yerləşdirsin və şəcərəni ortaq etsin.
Artıq şəcərə ortaq olduğundan, Anton öz zövqünü göstərməyə qərar verdi və bütün portretləri özü hazırladığı çərçivələrlə bəzədi. Axır vaxtlar bağçada çox gözəl çərçivələr düzəltməyi öyrənmişdi. Tezliklə kifayət qədər rəngarəng çərçivələri oldu. Katya evdə olmadığı vaxt Anton planını həyata keçirməyə başladı. O, əvvəlcə bütün yarpaqları — soldan birinci olanı başlamaqla — götürməyə başladı. (Yarpaqlar altşəcərəsi olmayan düyünlərdir.) Qopardığı portretləri üst-üstə yığaraq otağına apardı. Prosesi yalnız Katyanın portreti qaldıqda da davam etdirdi və nəhayət, onu da otağına apardı.
Elə həmin an Anton dəhşətlə başa düşdü ki, yığdığı portret yığınlarına baxaraq ağacı bərpa edə bilmir! Katya universitetdən qayıdacaq və Anton ciddi problem yaşayacağını başa düşdü. Antonun ağacı bərpa etməsinə kömək edin! Hər bir şəcərə düyünü Katyanın qeyd etdiyi bir hərf etiketi daşıyır. Hər bir düyün aşağıdakı şərtlərə uyğundur:
Sol altşəcərədəki bütün düyünlərin etiketləri, əlifba sırasına görə cari düyünün etiketindən əvvəl gəlir.
Sağ altşəcərədəki bütün düyünlərin etiketləri, əlifba sırasına görə cari düyünün etiketindən sonra gəlir.
Şəkildə ağacın nümunəsi və Antonun atdığı addımlar təsvir olunub.
Giriş faylında bir neçə sətir var, hər sətirdə çıxarılmış düyünlərin hərf etiketləri verilib. Son sətirdə '*' işarəsi yerləşir, bu da məlumat sətirlərinin sonunu göstərir.
Çıxış faylında ağacın strukturunu ifadə edən bir sətir verin və düyünləri aşağıdakı ardıcıllıqla yazın:
Ağac boşdursa, çıxış da boş olur.
Əgər ağac boş deyilsə, aşağıdakı ardıcıllıqla düyünlərin etiketlərini verin:
Kök düyünün etiketi,
Sol altşəcərənin məlumatı,
Sağ altşəcərənin məlumatı.
Əgər bir neçə düzgün həll mümkündürsə, istənilənini çıxış edə bilərsiniz.
Nümunə 1