vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
Фактори неравнотеже бинарног дрвета
Дефинишимо висину празног дрвета као 0, а непразног дрвета као број чворова од корена тог дрвета до њему најудаљенијег листа (рачунајући и корен и тај лист). Дефинишимо фактор равнотеже чвора бинарног дрвета као апсолутну разлику између висина његовог левог и десног поддрвета. Напиши програм који одређује највећи фактор равнотеже неког чвора учитаног бинарног дрвета.
Улаз
Празно бинарно дрво се задаје карактером -
, а непразно у
облику [k <levo> <desno>]
, где је
k
цео број (вредност у корену), а <levo>
и <desno>
су лево и десно поддрво записани у истом
формату.
Излаз
На стандардни излаз исписати вредност највећег фактора равнотеже.
Пример 1
Улаз
[1 [6 - -] [3 [2 [7 - [8 - -]] -] [4 - [5 - -]]]]
Излаз
3
Објашњење
Учитано дрво је приказано на слици.
![Бинарно дрво](https://petljamediastorage.blob.core.windows.net/root/Media/Default/Kursevi/Zbirka2/03 rekurzija/03 eliminacija_rekurzije/60 faktori_ravnoteze_binarnog_drveta/drvo.png)
Највећи фактор равнотеже је у корену – лево подрво је висине 1, а десно висине 4, па је фактор једнак 3.
Пример 2
Улаз
[1 [2 [3 [4 [5 [6 [7 [8 [9 [10 - -] -] -] -] -] -] -] -] -] -]
Излаз
9
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.