Opis dvojiškega drevesa
Pri programiranju nam pri reševanju problemov pogosto pride prav, da podatke predstavimo v obliki dvojiškega drevesa. Dvojiška drevesa so prostor za hranjenje podatkov, kjer vsak podatek shranimo v vozlišču, ki poleg podatka vsebuje tudi dva kazalca – enega na svojega desnega in enega na svojega levega sina (kazalca lahko kažeta tudi v prazno). Vozlišče, ki nima svojega očeta, imenujemo koren. Na sliki spodaj imamo primer dvojiškega drevesa s korenom, ki hrani podatek 14.
Oklepajni opis I
Strukturo dvojiškega drevesa se da v računik zapisati v več oblikah. Ena izmed njih je zapis z oklepaji (oklepajni zapis). Njegova definicija je rekurzivna:
Opis tega drevesa je niz
»[#podatek_v_korenu˽#OpisLevegaPoddrevesa˽OpisDesnegaPoddrevesa]«,
kjer smo znak ˽ med deli pisali zgolj zaradi preglednosti – v pravem opisu ni presledkov.
1. primer
Oklepajni opis zgoraj navedenega drevesa je:
[14[10[][]][19[15[][]][20[][]]]]
Če ga razdelimo na dele »14«, »[10[][]]« ter »[19[15[][]][20[][]]]«, se lepo vidi struktura opisa. Prvi niz opiše koren, drugi njegovo levo ter tretji desno poddrevo. Opazimo, da se pri gradnji podpisa toliko časa spuščamo po drevesu, dokler ne pridemo do vozlišča, ki nima sinov. Njegov opis znamo takoj zapisati (»[vrednost[][]]«), potem pa jih samo še zložimo skupaj.
2. primer
Podano imamo dvojiško drevo na spodnji sliki. Kakšen je njegov oklepajni opis?
Vemo, da je oklepajni opis tega drevesa sestavljen iz treh delov: njegovega korena ter opisov levega in desnega poddrevesa. Sestavimo zato najprej opise za levo in desno poddrevo, ter jih nato zložimo skupaj.
• opis levega poddrevesa se glasi »[3[1[][2[][]]][4[][]]]«
• opis desnega poddrevesa se glasi »[7[6[][]][9[8[][]][10[][]]]]«, kjer so z različnimi barvamo iznačeni deli opisa.
• celoten opis se tako glasi
[5[3[1[][2[][]]][4[][]][7[6[][]][9[8[][]][10[][]]]]].
3. primer
Zapiši algoritem metode, ki iz dvojiškega drevesa zgradi oklepajni opis in ga vrne kot rezultat.
niz oklepajniOpis(Dvojisko drevo d):
če je drevo prazno, vrnemo niz »[]«
sicer zgradimo opisa za levo in desno poddrevo:
opisLevo = oklepajniOpis(d.levoPoddrevo)
opisDesno = oklepajniOpis(d.desnoPoddrevo)
v = vrednost v korenu drevesa d
opis = »[v#opisLevo#opisDesno]«
(znaki # so uporabljeni le zaradi preglednosti)
vrni niz opis
1. naloga
Iz opisa drevesa z znaki opis levega poddrevesa
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo znake in da poznamo njegov oklepajni opis. Sestavite metodo, ki oklepajnega izpisa vrne oklepajni izpis levega poddrevesa. Če metodo uporabimo na opisu »[a[b[][]][c[d[][]][a[][]]]]«, nam mora vrniti niz »[b[][]]«.
Oklepajni izpis je sestavljen iz treh delov, eden izmed njih je opis, ki ga iščemo.
Pomoč v obliki algoritma: oklepajni opis je oblike
»[vrednost_v_korenu[opis_levega_poddrevesa][opis_desnega_poddrevesa]]«. Iz tega niza moramo le izluščiti drugi del (»[opis_levega_poddrevesa]« ter ga vrniti kot rezultat metode.
2. naloga
Iz opisa drevesa z znaki opis desnega poddrevesa
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo znake in da poznamo njegov oklepaji opis. Sestavite metodo, ki oklepajnega izpisa vrne oklepajni izpis desnega poddrevesa. Če metodo uporabimo na opisu »[a[b[][]][c[d[][]][a[][]]]]«, nam mora vrniti niz »[c[d[][]][a[][]]]«.
Oklepajni izpis je sestavljen iz treh delov, eden izmed njih je opis, ki ga iščemo.
3. naloga
Iz opisa drevesa s števili opis levega poddrevesa
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo cela števila. Sestavite metodo, ki oklepajnega izpisa vrne oklepajni izpis levega poddrevesa. Če metodo uporabimo na opisu »[14[10[][]][19[15[][]][20[][]]]]«, nam mora vrniti niz »[10[][]]«.
4. naloga
Iz opisa drevesa s števili opis desnega poddrevesa
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo cela števila. Sestavite metodo, ki oklepajnega izpisa vrne oklepajni izpis levega poddrevesa.
5. naloga
Iz opisa drevesa s števili podatek v korenu
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo cela števila. Sestavi metodo, ki iz danega opisa dvojiškega drevesa vrne podatek v korenu tega drevesa. Če je drevo prazno, naj vrne najmanjše celo število.
Opis s tabelo
Dvojiško drevo lahko predstavimo tudi s pomočjo tabele. Pri tem nam tabela služi kot skladišče za podatke v drevesu, strukturo drevesa pa nam določa položaj podatkov v tabeli. Podatki iz drevesa so v tabeli zloženi na naslednji način:
• Koren drevesa naj bo v tabeli na mestu z indeksom 1 (pazite na to, da se indeksi v tabeli začno števi z 0 – torej bo prvo mesto v tabeli nezasedeno).
• Če je nek podatek vozlišča a v tabeli na mestu z indeksom i, potem je koren levega poddrevesa vozlišča a v tabeli na mestu z indeksom 2*i, koren desnega poddrevesa vozlišča a pa na mestu z indeksom 2*i + 1.
• Pozorni bodite na to, da so pri tem opisu nekatera mesta v tabeli nezasedena, tako da bomo za opis drevesa z n vozlišči tipično potrebovali tabelo dolžine več od n.
Za dvojiško drevo
| je njegov opis s tabelo sledeč:
Kot vidite, iz tega opisa ni tako lahko razbrati opisa levega in desnega poddrevesa za dani koren, je pa zelo pripraven, če potrebujemo hitro poiskati sinove oz. prednike kateregakoli vozlišča v dvojiščem drevesu. |
V praksi je potrebno za shranjevanje »praznih« mest v tabeli tja zapisati podatek, ki se v drevesu ne pojavlja (da vem, da je tisto mesto prazno). Kadar kot podatke v vozliščih hranimo cela števila, je to običajno najmanjše ali največje možno celo število, ki ga še lahko predstavimo.
1. naloga
Iz oklepajnega v opis s tabelo
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo znake in da poznamo njegov oklepajni opis. Sestavite metodo, ki vam bo iz oklepajnega opisa vrnila opis s tabelo.
Če metodo uporabimo na opisu »[14[10[][]][19[15[][]][20[][]]]]«, dobimo zgornjo tabelo.
Pomoč v obliki algoritma:
vstaviVTabelo(kjeVstavljamoKoren, opis)
če je opis enak nizu »[]« (prazno drevo), ne naredimo ničesar
sicer razdelimo opis na tri dele koren, levi in desni opis.
v tabelo na mesto kjeVstavljamoKoren zapišemo vrednost korena
na enak način (rekurzivno) vstavimo v tabelo opis levega poddrevesa
(torej pokličemo vstaviVTabelo(kjeVstavljamo*2, opis levega poddrevesa)
na enak način (rekurzivno) vstavimo v tabelo opis desnegaga poddrevesa
(torej pokličemo vstaviVTabelo(kjeVstavljamo*2+1, opis desnega poddrevesa)
Oklepajni opis razdelimo na tri dele ter vsakega posebej vstavimo v tabelo. Paziti moramo še, kam v tabelo vstavimo vrednost korena: če koren drevesa vstavimo na mesto z indeksom i, potem koren levega poddrevesa vstavimo na mesto z indeksom 2*i in koren desnega poddrevesa na mesto z indeksom 2*i+1.
2. naloga
Iz tabelaričnega v oklepajni opis
Predpostavimo, da v vozliščih dvojiškega drevesa kot podatke hranimo znake in da poznamo tabelo, ki predstavlja njegov tabelarični opis. Sestavite metodo, ki vam vrne oklepajni opis tega dvojiškega drevesa.
Algoritem je popolnoma enak kot tisti za gradnjo oglepajnega drevesa, le da tukaj podatke iz levega in desnega poddrevesa preberemo iz tabele.
Urejenost dvojiškega drevesa
Dvojiško drevo je urejeno, če so vsi podatki v levem poddrevesu manjši od podatka v korenu, vsi podatki v desnem poddrevesu pa večji od podatka v korenu (če kot podatke hranimo števila je relacija večji-manjši natančno določena, v primeru objektov pa jo moramo sami določiti). Prazno dvojiško drevo je privzeto urejeno.
Nekaj primerov urejenih dreves:
| 
| 
|
Seveda pa dvojiška drevesa običajno niso urejena, kot nam pokažeta spodnja primera:
|
• Drevo ni urejeno, saj je podatek v desnem sinu korena (13) manjši od podatka v korenu (14). | 
• Drevo ni urejeno – problemi so pri vozlišču s podatkom 7 (oglej si njegovega desnega sina!) ter pri vozlišču s podatkom 5, saj bi vozlišče s podatkom 4 moralo biti v njegovem levem (in ne desnem) poddrevesu. |
1. naloga
Urejenost v oklepajnem opisu
Predpostavimo, da kot podatke v vozliščih dvojiškega drevesa hranimo cela števila. Dvojiško drevo smo predstavili v oklepajnem zapisu. Sestavite metodo, ki preveri urejenost tako podanega dvojiškega drevesa. Če je drevo urejeno naj vrne true , če ni urejeno pa false .
Problem boste najlažje rešili, če boste opis razbili na tri dela (vrednost v korenu, opis levega in opis desnega poddrevesa), ter jih rekurzivno pregledali. Pozorni bodite na to, da ne zadostuje preveriti le vrednosti v sinovih danega korena, ampak morate preveriti vse vrednosti v celotnem levem in desnem poddrevesu (glej drugi primer pri neurejenih drevesih, problem z vozliščem z vrednostjo 4).
2. naloga
Urejenost v tabelaričnem opisu drevesa s števili
Predpostavimo, da kot podatke v vozliščih dvojiškega drevesa hranimo cela števila ter da poznamo tabelo, ki predstavlja njegov tabelarični zapis. Sestavite metodo, ki preveri urejenost tako podanega dvojiškega drevesa. Če je drevo urejeno naj vrne true , če ni urejeno pa false.
Postopamo enako kot pri prejšnji nalogi, le da je sedaj poddrevo določeno z indeksom njegovega korena v tabeli ter ne več z opisom.
3. naloga
Največji v urejenem drevesu (oklepajni zapis)
Predpostavimo, da kot podatke v vozliščih dvojiškega drevesa hranimo male črke, ter da je drevo že urejeno. Predstavili smo ga v oklepajnem zapisu. Sestavite metodo, ki vrne največji znak v drevesu. Če je drevo prazno, vrni veliki A.
Premislite, kje v urejenem drevesu leži največji znak.
Kadar si v dvomih, zavij desno.
4. naloga
Najmanjši v urejenem drevesu (oklepajni zapis)
Predpostavimo, da kot podatke v vozliščih dvojiškega drevesa hranimo cela števila, ter da je drevo že urejeno. Predstavili smo ga v oklepajnem zapisu. Sestavite metodo, ki vrne najmanjše število v drevesu. Če je drevo prazno, vrni največje možno celo število.
Premislite, kje v urejenem drevesu leži najmanjše število.
Kadar si v dvomih, zavij levo.
Vmesni oklepajni zapis
Poleg običajnega, poznamo še nekaj drugih oklepajnih opisov dvojiškega drevesa. Eden izmed njih je vmesni oklepajni opis:
1. primer
Za drevo
je njegov vmesni oklepajni opis »{{{}10{}}14{{{}15{}}13{{}20{}}}}«.
2. primer
Za drevo
je vmesni oklepajni opis enak »{{{{}-5{}}1{{}7{}}}8{{}13{{}21{}}}}«.
1. naloga
Iz oklepajnega v vmesni oklepajni zapis
Sestavite metodo, ki iz oklepajnega zapisa dvojiškega drevesa naredi vmesni oklepajni zapis.
Če jo pokličemo z opisom [14[10[][]][19[15[][]][20[][]]]], mora vrniti vmesni oklepajni opis {{{}10{}}14{{{}15{}}19{{}20{}}}}.
Pomoč v obliki algoritma:
izObicajnegaVVmesni(obicajniOpis)
če običajni opis predstavlja prazno drevo, vrni niz »{}«
sicer razbil opis na tri dele:
vrednost = vrednost korena
levi = običajni oklepajni opis levega poddrevesa
desni = običajni oklepajni opis levega poddrevesa
rekurzivno izračunaj vmesni oklepajni opis levega in desnega poddrevesa
ter shrani njune vrednosti v leviVmesni ter desniVmesni
(leviVmesni = izObicajnegaVVmesni(levi), podobno za desnega)
vrni leviVmesni + vrednost + desniVmesni, kjer + predstavlja operator
sklapljanja nizov.
Običajno oklepajni opis razbijte na vrednost v korenu ter običajna oklepajna opisa za levo in desno poddrevo. Nato rekurzivno izračunajte vmesne opise za levo ter desno poddrevo ter jih pravilno zložite skupaj.
2. naloga
Iz vmesnega oklepajnega v navadni oklepajni zapis
Sestavite metodo, ki iz vmesnega oklepajnega zapisa naredi navadni oklepajni zapis. Če jo pokličemo z vmesnim opisom {{{}10{}}14{{{}15{}}19{{}20{}}}}, mora vrniti običajni oklepajni opis [14[10[][]][19[15[][]][20[][]]]].
Razmišljamo enako kot zgoraj, le »obrnjeno«.
3. naloga
Iz vmesnega oklepajnega v tabelarični zapis
Sestavite metodo, ki iz vmesnega oklepajnega zapisa naredi tabelarični zapis.
Če jo pokličemo z vmesnim opisom {{{}10{}}14{{{}15{}}19{{}20{}}}}, mora vrniti tabelo
Metoda je zelo podobna tisti, ki v tabelarični zapis prevede običajni oklepajni opis.
