Çox Darıxdırıcı Ev Tapşırığı

Prof. Z düşünür ki, ev tapşırığını onun tələbələrinin əksəriyyəti üçün həll etmək çox çətindir (siz "Darixdirici ev tapşırığı" məsələsini xatırlayırsınızmı?). Onun təəccübünə görə, bir çox tələbə düzgün həllər təqdim edir. O, bunun məsələnin asan olmasına görə deyil, test məlumatlarının çox az olduğuna görə baş verdiyinə inanır. Buna görə, o, eyni tapşırığı yenidən verməyə qərar verir, lakin bu dəfə çox böyük test halları ilə. Təbii ki, tələbələri indi bu ev tapşırığını daha da darıxdırıcı hesab edirlər. Onların yenidən köməyinizə ehtiyacı var.

Keçən dəfə Prof. Z-nin verdiyi tapşırığı xatırlamayanlar üçün:

Sizdən ikili axtarış ağacının (BST) qrafikini çəkmək tələb olunur.

İkili axtarış ağacı (bəzən sıralı və ya qaydalı ikili ağac da adlanır) aşağıdakı xüsusiyyətlərə malik olan qovşaq əsaslı ikili ağac məlumat strukturu növüdür: Qovşağın sol alt ağacı yalnız qovşağın açarından kiçik açarlı qovşaqlardan ibarətdir. Qovşağın sağ alt ağacı isə yalnız qovşağın açarından böyük açarlı qovşaqlardan ibarətdir. Həm sol, həm də sağ alt ağaclar da ikili axtarış ağacı olmalıdır.

Verilmiş tam ədədlər siyahısını ardıcıllıqla boş bir BST-yə bir-bir daxil edin, nəticədə unikal bir BST yaranacaq. Prof. Z tələbələrdən bu BST-nin qrafikini çəkməyi istəyir.

BST-nin çəkilməsi qaydaları aşağıdakılardır:

1. 1 qovşaqlı BST-nin qrafiki tək 'o' (15-ci kiçik latın hərfi) olur.

2. Əgər BST-də boş olmayan alt ağac varsa, alt ağacın kökünün birbaşa yuxarısında bir dənə '|', onun üzərində isə bir dənə '+' çəkilir. '+' olan sətirdə, alt ağacın '+' (sol və ya sağ alt ağac üçün) qeydini və 'o'-nu (alt ağacların valideynini) birləşdirmək üçün mümkün olan ən az (bəzən 0) sayda '-' istifadə olunur.

3. Sol alt ağac (əgər varsa) mütləq valideynin solunda çəkilməlidir. Eyni qayda ilə, sağ alt ağac (əgər varsa) valideynin sağında olmalıdır.

4. BST-nin kökünün sütununda heç bir sol və ya sağ alt ağacın xarakteri olmamalıdır.

5. BST-nin hər bir qovşağı üçün, onun sol və sağ alt ağaclarının qrafiklərində heç bir sütun bütün ağacın şəklində üst-üstə düşməməlidir.

Bütün BST çəkildikdən sonra, sətirlər yuxarıdan aşağıya 1-dən, sütunlar isə soldan sağa 1-dən nömrələnir.

Ağac çox böyük ola biləcəyi üçün, çəkilən şəkil Prof. Z üçün bütövlükdə baxış üçün çox böyük ola bilər. Buna görə, sizdən bütün şəkil əvəzinə yalnız $m$ fraqment təqdim etməyiniz tələb olunur.