B - Binárny Vyhľadávací Strom

Filip a Branko sa na 4. prednáške z predmetu "Programovanie, Algoritmy a Zložitosť" dozvedeli o binárnych vyhľadávacích stromoch (BVS). Keďže Branko si nevedel predstaviť ako to funguje pre väčšie počty čísel, tak poprosil Filipa o vysvetlenie. Ten, ako správny informatik, napísal program, ktorý generuje úplné BVS. Na zobrazenie stromovej štruktúry využil odsadenie a rozhodol sa ukázať v akom poradí sú čísla v tomto BVS od najmenšieho. Ale potreboval by svoj výpis skontrolovať, či neurobil niekde chybu (predsa je ešte len prvákom na vysokej škole).

Z poznámok si zhrnul vlastnosti BVS:

• ide o graf, teda množinu vrcholov a hrán
• strom nemá žiadne cykly, je súvislý (z každého vrcholu sa dá dostať do každého iného)
• strom môžeme zakoreniť, teda jeden vrchol prehlásiť za koreň
• v binárnom strome má každý vrchol najviac 2 potomkov (susedov v smere od koreňa) a práve jedného rodiča (okrem koreňa)
• pre binárny vyhľadávací strom platí, že hodnoty v ľavom podstrome sú menšie a v pravom podstrome väčšie ako hodnota vo vrchole
• úrovňou stromu nazývame vrcholy, ktoré sú rovnako vzdialené od koreňa
• úplný binárny strom je strom, kde všetky vrcholy (okrem poslednej úrovne) majú práve dvoch potomkov

Vašou úlohou je napísať program, ktorý vygeneruje niektoré riadky z takéhoto BVS na kontrolu.

Úloha

Vstup

Výstup

Príklad

Vstup:

4 4
2 4 3 1

Výstup:

......04..............12
01..03..05..07..09..11..13..15
..02......06......10......14
..............08