5. Binárne stromy¶

Pripomeňme si, ako sme doteraz pracovali so spájaným zoznamom:

spájaný zoznam sa skladal z vrcholov, ktoré boli navzájom pospájané smerníkmi (referenciami, pointermi)
zoznam bol prístupný cez referenciu na prvý vrchol
každý vrchol, okrem posledného mal svojho jediného nasledovníka (atribút next)
pre dvojsmerný spájaný zoznam každý vrchol okrem prvého mál v zozname svojho predchodcu - už vieme, že keď chceme zrušiť zo zoznamu nejaký vrchol, musíme meniť aj nasledovníka predchodcu …

Používali sme takúto deklaráciu vrcholu:

class Vrchol:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

Na postupné prechádzanie všetkých vrcholov zoznamu nám stačil takýto jednoduchý while-cyklus:

pom = zac               # začiatok zoznamu
while pom is not None:
    print(pom.data)     # spracuje vrchol
    pom = pom.next

Túto schému prechádzania prvkov vieme využiť aj na zisťovanie počtu prvkov, na zisťovanie, či sa nejaká hodnota nachádza v zozname, na vyhadzovanie niektorých existujúcich, resp. pridávanie nových vrcholov.

Spájané zoznamy sú najjednoduchším prípadom spájaných štruktúr, pre ktoré sú prvky spájané referenciami (smerníkmi).

Ďalšou spájanou dátovou štruktúrou je strom (tree), o ktorej sa zvykne hovoriť, že je to hierarchická dátová štruktúra.

Kde všade môžeme vidieť stromovú dátovú štruktúru:

rodokmeň, napríklad potomkovia bývalej anglickej kráľovnej Alžbety II:
- z tabuľky potomkov na wikipédii môžeme pripraviť takéto grafické zobrazenie:
  
  vidíme, že kráľovná má štyroch potomkov (troch synov a jednu dcéru), tieto jej deti majú ďalších potomkov (vnukov aj vnučky) a tiež pravnukov a pravnučky
- veľmi zaujímavý je aj graf jej predkov na wikipédii
  
  v tomto grafe má každá osoba (v strede vľavo je anglická kráľovná Alžbeta II. s číslom 1) práve dvoch rodičov: otec je horná osoba (s číslom 2) a matka je dolná osoba (s číslom 3); osoby s číslami 4 až 7 sú štyria starí rodičia súčasnej kráľovnej; osoby s číslami 8 až 15 sú prastarí rodičia; všimnite si, že v každej ďalšej úrovni (v ďalšej generácii) tohto zobrazenia je dvojnásobný počet osôb z predchádzajúcej úrovne (každá osoba má práve dvoch rodičov)
štruktúra adresárov (priečinkov) na disku: nejaký adresár je domovský a ten môže mať pod sebou niekoľko podadresárov, niektoré z nich môžu opäť obsahovať ďalšie podadresáre, …
štruktúra fakulty: naša fakulta sa skladá zo štyroch skupín odborných katedier (matematickej, fyzikálnej, informatickej a didaktickej) a ďalšími pracoviskami, každá sekcia sa skladá z niekoľkých katedier a väčšina katedier sa ešte delí na oddelenia
štruktúra učebnice, manuálu: materiály sa skladajú z kapitol, tie z podkapitol a rôznych podčastí
hierarchia objektových tried: z bázovej triedy môžeme odvodiť niekoľko ďalších a aj z týchto odvodených tried môžeme vytvárať ďalšie triedy, napríklad v prednáške 16. Triedy a dedičnosť sme zo základnej triedy turtle.Turtle vytvorili triedu MojaTurtle a z nej sme postupne vytvárali triedy MojaTurtle1, MojaTurtle2 a MojaTurtle3

Aj všetky tieto ďalšie štruktúry by sme vedeli zakresliť do tvaru stromovej štruktúry, ktorá má nejaký počiatočný vrchol (napríklad kráľovná, domovský adresár, fakulta, kniha, bázová trieda, …) a z tohto vrcholu vychádzajú ďalšie a ďalšie vrcholy (potomkovia, podadresáre, sekcie, kapitoly, …).

Všeobecný strom¶

Spájaná dátová štruktúra strom je zovšeobecnením spájaného zoznamu:

skladá sa z množiny vrcholov, v každom vrchole sa nachádza nejaká informácia (napríklad atribút data)
vrcholy sú navzájom pospájané hranami:
- jeden vrchol má špeciálne postavenie: je prvý a od neho sa vieme dostať ku všetkým zvyšným vrcholom
- každý vrchol okrem prvého má práve jedného predchodcu
- každý vrchol môže mať ľubovoľný počet nasledovníkov (nie iba jeden, ako to bolo pri spájaných zoznamoch)

Napríklad, v takomto strome:

jediný vrchol C nemá predchodcu, všetky ostatné vrcholy majú práve jedného predchodcu. Niektoré vrcholy (D a L) majú len jedného nasledovníka, niektoré (A, B a M) majú dvoch nasledovníkov, dva vrcholy C a F majú až troch nasledovníkov. Všetky zvyšné vrcholy nemajú ani jedného nasledovníka.

Zvykne sa používať takáto terminológia z botaniky:

koreň (root) je špeciálny prvý vrchol - jediný nemá svojho predchodcu (vrchol C)
vetva (branch) je hrana (budeme ju kresliť šípkou) označujúca nasledovníka
list (leaf) označuje vrchol, ktorý už nemá žiadneho nasledovníka (listami tohto stromu sú vrcholy E, G, H, I, J, K, O a P)

Okrem botanickej terminológie sa pri stromoch používa aj takáto terminológia rodinných vzťahov:

predchodca každého vrcholu (okrem koreňa) sa nazýva rodič, predok, niekedy aj otec (parent, ancestor)
nasledovník vrcholu sa nazýva potomok alebo dieťa, niekedy aj syn (descendant, child)
vrcholy, ktoré majú spoločného predchodcu (predka) sa nazývajú súrodenci (siblings), napríklad A, B, L sú súrodenci, ale I a M súrodencami nie sú

Ďalej sú dôležité ešte aj tieto pojmy:

okrem listov sa v strome môžu nachádzať aj vnútorné vrcholy (interior nodes), to sú tie, ktoré majú aspoň jedného potomka (v našom príklade sú to A, B, C, D, F, L, M)
medzi dvoma vrcholmi môžeme vytvárať cesty, t.j. postupnosti hrán, ktoré spájajú vrcholy - samozrejme, že len v smere od predkov k potomkom (v smere šípok) - dĺžkou cesty je počet týchto hrán (medzi rodičom a dieťaťom je cesta dĺžky 1), napríklad cesta C - A - F - G má dĺžku 3
úroveň, alebo hĺbka vrcholu (level, depth) je dĺžka cesty od koreňa k tomuto vrcholu, teda koreň má hĺbku 0, jeho deti majú hĺbku 1, ich deti (vnuci/vnučky) ležia na úrovni 2, atď. (na 2. úrovni stromu ležia vrcholy D, F, I, K, M)
výška stromu (height) je maximálna úroveň v strome, t.j. dĺžka najdlhšej cesty od koreňa k listom (strom v našom príklade má výšku 3)
podstrom (subtree) je časť stromu, ktorá začína v nejakom vrchole a obsahuje všetkých jeho potomkov (nielen deti, ale aj ich potomkov, …), napríklad strom s vrcholmi L, M, O, P je podstrom výšky 2 a podstrom s vrcholmi E, F, G, H má výšku 1
šírka stromu (width) je počet vrcholov v úrovni, v ktorej je najviac vrcholov (strom v našom príklade má šírku 6)

Niekedy sa všeobecný strom definuje aj takto rekurzívne:

strom je buď prázdny (neobsahuje žiadny vrchol), alebo
obsahuje koreň a množinu podstromov, ktoré vychádzajú z tohto koreňa, pričom každý podstrom je opäť všeobecný strom (ak nie je prázdny, má svoj koreň a aj svoje podstromy)

Binárny strom¶

má dve extra vlastnosti:

každý vrchol má maximálne dvoch potomkov
rozlišuje medzi ľavým a pravým potomkom - budeme to kresliť buď šípkou šikmo vľavo dole alebo šikmo vpravo dole

Napríklad, takýto binárny strom:

Vrchol b nemá ľavého potomka, len pravého. Rovnako je na tom aj vrchol e. Vrchol f má len ľavého potomka a nemá pravého. Všetky ostatné vrcholy sú buď listami (nemajú žiadne deti) alebo majú oboch potomkov, ľavého aj pravého.

Aj binárny strom môžeme definovať rekurzívne:

je buď prázdny,
alebo sa skladá z koreňa a z dvoch jeho podstromov: z ľavého podstromu a pravého podstromu, tieto sú opäť binárne stromy (môžu byť aj prázdne)

Všetko, čo platí pre všeobecné stromy, platí aj pre binárne, t.j. má koreň, má rodičov a potomkov, má listy aj vnútorné vrcholy, má cesty aj úrovne, hovoríme o hĺbke vrcholov aj výške stromu.

Zamyslime sa nad maximálnym počtom vrcholov v jednotlivých úrovniach:

v 0. úrovni môže byť len koreň, teda len 1 vrchol
koreň môže mať dvoch potomkov, teda v 1. úrovni môžu byť maximálne 2 vrcholy
v 2. úrovni môžu byť len deti predchádzajúcich dvoch vrcholov v 1. úrovni, teda maximálne 4 vrcholy
v každej ďalšej úrovni môže byť maximálne dvojnásobok predchádzajúcej, teda v i-tej úrovni môže byť maximálne 2**i vrcholov
strom, ktorý má výšku h môže mať maximálne 1 + 2 + 4 + 8 + … + 2**h vrcholov, teda spolu 2**(h+1)-1 vrcholov
- strom s maximálnym počtom vrcholov s výškou h sa nazýva úplný strom

Napríklad:

Tento strom má výšku 3 a preto počet všetkých vrcholov je 1 + 2 + 4 + 8 = 15, čo je naozaj 2**4-1

Realizácia spájanou štruktúrou¶

Binárny strom budeme realizovať podobne ako spájaný zoznam, t.j. najprv definujeme triedu Vrchol, v ktorej sa definujú atribúty každého prvku binárneho stromu:

class Vrchol:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

Na rozdiel od spájaného zoznamu, tento vrchol binárneho stromu má namiesto jedného nasledovníka next dvoch nasledovníkov: ľavého left a pravého right. Vytvorme najprv 3 izolované vrcholy:

>>> a = Vrchol('A')
>>> b = Vrchol('B')
>>> c = Vrchol('C')

Tieto tri vrcholy môžeme chápať ako 3 jednovrcholové stromy. Pomocou priradení môžeme pripojiť stromy b a c ako ľavý a pravý podstrom vrcholu a:

>>> a.left = b
>>> a.right = c

Takto vytvorený binárny strom má 3 vrcholy, z toho 2 sú listy a jeden (koreň) je vnútorný. Výška stromu je 1 a šírka 2. V 0. úrovni je jeden vrchol 'A', v 1. úrovni je 'B' a 'C'.

Takýto istý strom vieme vytvoriť jediným priradením:

>>> a = Vrchol('A', Vrchol('B'), Vrchol('C'))

Ak chceme teraz vypísať hodnoty vo vrcholoch tohto stromu, môžeme to urobiť, napríklad takto:

>>> print(a.data, a.left.data, a.right.data)
    A B C

Ak by bol strom trochu komplikovanejší, výpis vrcholov by bolo dobre nejako zautomatizovať. Napríklad, takýto strom:

>>> a = Vrchol('A', Vrchol('B', Vrchol(1), Vrchol(2)), Vrchol('C', None, Vrchol(3)))

Tento strom so 6 vrcholmi má už výšku 2, pričom v druhej úrovni sú tri vrcholy: 1, 2 a 3.

Nakreslenie stromu¶

Strom nakreslíme rekurzívne. Prvá verzia bez kreslenia čiar:

import tkinter
canvas = tkinter.Canvas(width=400, height=400)
canvas.pack()

def kresli(v, sir, x, y):
    if v is not None:
        canvas.create_text(x, y, text=v.data)
        kresli(v.left, sir/2, x-sir/2, y+40)
        kresli(v.right, sir/2, x+sir/2, y+40)

Prvým parametrom funkcie je koreň stromu (teda referencia na najvrchnejší vrchol stromu). Druhým parametrom je polovičná šírka grafickej plochy. Ďalšie dva parametre sú súradnicami, kde sa nakreslí koreň stromu. Všimnite si, že v rekurzívnom volaní:

smerom vľavo budeme vykresľovať ľavý podstrom, preto x-ovú súradnicu znížime o polovičnú šírku plochy, y-ovú zvýšime o nejakú konštantu, napríklad 40
smerom vpravo budeme kresliť pravý podstrom a teda x-ovú súradnicu zväčšíme tak, aby bola v polovici šírky oblasti

Môžete to vyskúšať, napríklad, pre takýto strom:

strom = Vrchol('A', Vrchol('B', Vrchol(1), Vrchol(2)), Vrchol('C', None, Vrchol(3)))
kresli(strom, 200, 200, 40)

Ak by sme chceli kresliť aj hrany stromu (spojnice medzi vrcholmi), môžeme to zapísať, napríklad takto (táto druhá verzia má ešte chyby):

def kresli(v, sir, x, y):
    canvas.create_text(x, y, text=v.data)
    if v.left is not None:
        kresli(v.left, sir/2, x-sir/2, y+40)
        canvas.create_line(x, y, x-sir/2, y+40)
    if v.right is not None:
        kresli(v.right, sir/2, x+sir/2, y+40)
        canvas.create_line(x, y, x+sir/2, y+40)

Takéto vykresľovanie stromu má ale tú chybu, že nakreslené hrany (čiary) prechádzajú cez vypísané hodnoty vo vrcholoch. Opravíme to tak, že nakreslenie samotného vrcholu (bude to teraz farebný krúžok s textom) presťahujeme až na koniec funkcie, kreslenie čiar bude naopak ako prvé, aby nakreslené krúžky tieto čiary prekryli:

def kresli(v, sir, x, y):
    if v.left is not None:
        canvas.create_line(x, y, x-sir/2, y+40)
        kresli(v.left, sir/2, x-sir/2, y+40)
    if v.right is not None:
        canvas.create_line(x, y, x+sir/2, y+40)
        kresli(v.right, sir/2, x+sir/2, y+40)
    canvas.create_oval(x-15, y-15, x+15, y+15, fill='white')
    canvas.create_text(x, y, text=v.data, font='consolas 12')

Opäť otestujte aj túto vylepšenú verziu.

Zrejme, neskôr si budete túto verziu rôzne prispôsobovať:

budete kresliť strom na iný rozmer plochy
niektoré farebné krúžky môžete prefarbiť podľa obsahu, resp. polohy vrcholu
hrany sa môžu kresliť ako šípky a nie ako úsečky

Generovanie náhodného stromu¶

Využijeme náhodný generátor random.randrange. Princíp tejto funkcie je nasledovný:

pridávať budeme len do neprázdneho stromu (strom musí obsahovať aspoň koreň)
funkcia sa najprv rozhodne, či bude pridávať do ľavého alebo do pravého podstromu (test random.randrange(2) testuje, či má náhodné číslo z množiny {0, 1} hodnotu 1, teda je to pravdepodobnosť 50%)
ďalej zistí, či daný podstrom existuje (napríklad, vrch.left is None označuje, že neexistuje), ak nie, tak na jeho mieste vytvorí nový vrchol s danou hodnotou
ak podstrom na tomto mieste už existuje, znamená to, že tu nemôžeme „zavesiť“ nový vrchol, ale musíme preň hľadať nové miesto, preto sa toto hľadanie opakuje už od nového vrcholu (nižšie uvidíme aj rekurzívnu verziu, pri ktorej sa pridávanie vrcholu do tohto podstromu zrealizuje rekurzívnym volaním)

Najprv nerekurzívna verzia funkcie:

import random

def pridaj_vrchol(vrch, hodnota):
    while True:
        if random.randrange(2):
            if vrch.left is None:
                vrch.left = Vrchol(hodnota)
                return
            vrch = vrch.left
        else:
            if vrch.right is None:
                vrch.right = Vrchol(hodnota)
                return
            vrch = vrch.right

Teraz rekurzívna verzia:

def pridaj_vrchol(vrch, hodnota):
    if random.randrange(2):
        if vrch.left is None:
            vrch.left = Vrchol(hodnota)
        else:
            pridaj_vrchol(vrch.left, hodnota)
    else:
        if vrch.right is None:
            vrch.right = Vrchol(hodnota)
        else:
            pridaj_vrchol(vrch.right, hodnota)

Môžeme otestovať:

koren = Vrchol(random.randint(1, 20))
for h in range(20):
    pridaj_vrchol(koren, random.randint(1, 20))

alebo:

strom = Vrchol('p')
for i in 'rogramovanie':
    pridaj_vrchol(strom, i)

Tieto testy spustite viackrát a zakaždým strom vykreslite (pomocou funkcie kresli). Uvidíte rôzne usporiadania vrcholov v strome a tieto budú mať možno rôzne výšky.

Ďalšie rekurzívne funkcie¶

Tieto funkcie budú rekurzívne prechádzať všetky vrcholy v strome: najprv v ľavom podstrome a potom aj v pravom.

Uvádzame dve verzie súčtu hodnôt vo vrcholoch. Prvá verzia, keď zistí, že je strom neprázdny, vypočíta súčet najprv v ľavom podstrome a potom aj v pravom. Výsledkom celej funkcie je potom súčet hodnoty v koreni stromu + súčet všetkých hodnôt v ľavom podstrome + súčet všetkých hodnôt v pravom podstrome:

def sucet(vrch):
    if vrch is None:
        return 0
    vlavo = sucet(vrch.left)
    vpravo = sucet(vrch.right)
    return vrch.data + vlavo + vpravo

print('sucet =', sucet(koren))

Skúsenejší programátori túto funkciu vedia zapísať aj takto „úspornejšie“:

def sucet(vrch):
    if vrch is None:
        return 0
    return vrch.data + sucet(vrch.left) + sucet(vrch.right)

Otestujte túto funkciu na náhodne generovaných stromoch, napríklad:

strom = Vrchol(random.randint(1, 20))
for i in range(20):
    pridaj_vrchol(strom, random.randint(1, 20))
kresli(strom, 200, 200, 40)
print('sucet hodnot =', sucet(strom))

Na veľmi podobnom princípe pracuje aj zisťovanie celkového počtu vrcholov v strome:

def pocet(vrch):
    if vrch is None:
        return 0
    return 1 + pocet(vrch.left) + pocet(vrch.right)

print('pocet vrcholov =', pocet(strom))

Ďalej budeme zisťovať výšku stromu (opäť bude niekoľko verzií). Najprv verzia, ktorá ešte nie je tá správna:

def vyska(vrch):
    if vrch is None:
        return 0
    vyska_vlavo = vyska(vrch.left)
    vyska_vpravo = vyska(vrch.right)
    return 1 + max(vyska_vlavo, vyska_vpravo)

Funkcia najprv rieši situáciu, keď je strom prázdny: vtedy dáva výsledok 0. Keď nie je strom prázdny, najprv sa vypočíta výška ľavého podstromu, potom aj výška pravého podstromu. Na záver sa z týchto dvoch výšok vyberie tá väčšia a k tomu sa ešte pripočíta 1, lebo celkový strom okrem dvoch podstromov obsahuje aj koreň, ktorý je o úroveň vyššie.

Táto funkcia ale nedáva správne výsledky. Keď ju otestujete, zistíte, že dostávate o 1 väčšiu hodnotu, ako je skutočná výška. Napríklad:

>>> strom = Vrchol(1)
>>> vyska(strom)
    1
>>> strom = Vrchol(1, Vrchol(2), Vrchol(3))
>>> vyska(strom)
    2

Pripomíname, že výška je počet hrán na ceste od koreňa k najnižšiemu vrcholu (k nejakému listu). Strom, ktorý obsahuje len koreň, by mal mať výšku 0 a strom, ktorý má koreň a dvoch jeho potomkov, má dve takéto cesty (od koreňa k listom) a obe majú dĺžku 1 (len 1 hranu). Problémom v tomto riešení je výška prázdneho stromu: tá nemôže by 0, lebo 0 je pre strom s 1 vrcholom. Dohodneme sa, že výškou prázdneho stromu bude -1 a potom to už bude celé fungovať správne:

def vyska(vrch):
    if vrch is None:
        return -1
    vyska_vlavo = vyska(vrch.left)
    vyska_vpravo = vyska(vrch.right)
    return 1 + max(vyska_vlavo, vyska_vpravo)

alebo druhá verzia, ktorá si výšky jednotlivých podstromov nepočíta do pomocných premenných, ale priamo ich pošle do štandardnej funkcie max():

def vyska(vrch):
    if vrch is None:
        return -1             # pre prázdny strom
    return 1 + max(vyska(vrch.left), vyska(vrch.right))

print('vyska =', vyska(strom))

Výpis hodnôt vo vrcholoch v nejakom poradí:

def vypis(vrch):
    if vrch is None:
        return
    print(vrch.data, end=' ')
    vypis(vrch.left)
    vypis(vrch.right)

vypis(strom)

Vo výpise sa objavia hodnoty vo všetkých vrcholoch v nejakom poradí.

Metóda repr¶

Veľmi zaujímavo sa správa metóda __repr__(), ktorú zapíšeme priamo v triede Vrchol:

class Vrchol:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

    def __repr__(self):
        return f'Vrchol({self.data!r}, {self.left}, {self.right})'

Otestujeme:

>>> strom = Vrchol(1, Vrchol(2, Vrchol(4)), Vrchol(3))
>>> strom
    Vrchol(1, Vrchol(2, Vrchol(4, None, None), None), Vrchol(3, None, None))

Vidíte, že táto metóda je rekurzívna, pričom Python tu správne zvláda aj triviálny prípad.

Cvičenia¶

Do premennej strom sme priradili binárny strom. Nakresli ho na papier (bez počítača)

class Vrchol:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

>>> strom = Vrchol(7,Vrchol(13,None,Vrchol(5,Vrchol(8))),Vrchol(2,Vrchol(11,Vrchol(19)),Vrchol(3)))

Skontroluj svoju kresbu s vykreslením pomocou kresli(), napríklad pomocou tejto verzie funkcie:

def kresli(vrch, sir, x, y):
    if vrch.left is not None:
        canvas.create_line(x, y, x-sir/2, y+40)
        kresli(vrch.left, sir/2, x-sir/2, y+40)
    if vrch.right is not None:
        canvas.create_line(x, y, x+sir/2, y+40)
        kresli(vrch.right, sir/2, x+sir/2, y+40)
    canvas.create_oval(x-15, y-15, x+15, y+15, fill='white')
    canvas.create_text(x, y, text=vrch.data, font='consolas 12')

Do premennej strom priraď binárny strom, ktorý po vykreslení vyzerá takto:

Napríklad:
```
strom = ...
kresli(strom, ...)
```
Najprv bez počítača odpovedz, aká je výška tohto stromu? Potom to skontroluj pomocou:
```
def vyska(vrch):
    if vrch is None:
        return -1             # pre prázdny strom
    return 1 + max(vyska(vrch.left), vyska(vrch.right))
```
Pre daný strom odpovedz na tieto otázky:
- koľko má vnútorných vrcholov a koľko listov?
- koľko vrcholov má ľavý podstrom s koreňom F a koľko pravý podstrom s koreńom B?
- aká je výška ľavého aj pravého podstromu (skontroluj to aj pomocou funkcie vyska())?
- ktoré vrcholy sa nachádzajú v 0. úrovni, ktoré v 1. úrovni, ktoré v 2. a v 3. úrovniach?
- aká je šírka tohto stromu?
- vymenuj všetky cesty z vrcholu F do listov stromu

Nakresli aj tento strom a zisti, aká je jeho výška:
- zrejme najprv priradíš tento strom do premennej a potom zavoláš kresli()
- výšku skontroluj pomocou funkcie vyska()
- aká je šírka tohto stromu (zatiaľ bez funkcie)?

Uprav funkciu kresli() tak, aby sa listy stromu kreslili 'lightgreen' farbou a vnútorné vrcholy 'lightblue'. Napríklad takto:

Nakresli taký binárny strom, ktorý má práve 6 listov a v týchto listoch sú postupne zľava doprava písmená zo slova 'Python', zvyšné vnútorné vrcholy stromu obsahujú znak bodku '.'. Tento strom priraď do premennej a skontroluj:
```
strom = ...
kresli(strom, ...)
```
- Navrhni taký strom (opäť s písmenami 'Python'), ktorého všetky listy majú rovnakú vzdialenosť od koreňa (tzv. hĺbka vrcholu). Priraď tento strom do premennej a nakresli.
- Navrhni taký strom, ktorého všetky listy majú navzájom rôznu vzdialenosť od koreňa: vrchol 'P' bude mať vzdialenosť 1, vrchol 'y' vzdialenosť 2, vrchol 't' vzdialenosť 3, … Priraď tento strom do premennej a nakresli.

Navrhni také binárne stromy, ktoré majú presne 6 vrcholov (hodnoty vo vrcholoch nás teraz nezaujímajú, môžu to byť prázdne reťazce), ale
1. má len 1 list
2. má 2 listy, ale maximálnu možnú výšku
3. má 2 listy, ale minimálnu možnú výšku
4. má maximálny možný počet listov
Tieto štyri stromy zadefinuj ako pythonovskú štruktúru strom a vykresliť pomocou kresli().

Napíš funkciu vyrob_strom(postupnost), ktorá vytvorí náhodný binárny strom z prvkov zadanej neprázdnej postupnosti. Koreňom stromu bude prvý vrchol postupnosti. Funkcia vráti referenciu na koreň stromu. Využi túto ideu nerekurzívnej funkcie z prednášky:

def pridaj_vrchol(vrch, hodnota):
    while True:
        if random.randrange(2):
            if vrch.left is None:
                vrch.left = Vrchol(hodnota)
                return
            vrch = vrch.left
        else:
            if vrch.right is None:
                vrch.right = Vrchol(hodnota)
                return
            vrch = vrch.right

Napríklad, volanie vyrob_strom('Python') vytvorí náhodný strom so 6 vrcholmi - tento strom vykresli a vypíš výšku stromu aj počet vrcholov pomocou funkcie pocet:

def pocet(vrch):
    if vrch is None:
        return 0
    return 1 + pocet(vrch.left) + pocet(vrch.right)

Skontroluj aj volanie vyrob_strom(range(1000)) a vypíš výšku tohto stromu aj počet jeho vrcholov.

Napíš funkciu pocet_listov(vrch), ktorá pre daný binárny strom zistí počet listov. Funkcia sa bude podobať funkcii pocet(vrch). Funkcia bude zrejme rekurzívna a bude riešiť tieto prípady:
- pre prázdny strom bude výsledkom 0
- pre vrchol, ktorý je listom (ľavý aj pravý podstrom je None), bude výsledkom 1
- inak zistí počet listov v ľavom podstrome a aj počet listov v pravom podstrome, tieto dva výsledky spočíta a tento súčet je výsledným počtom listov v celom strome
Funkciu skontroluj aj pre niektoré stromy z predchádzajúcich úloh. Napríklad:
```
>>> strom = Vrchol(7,Vrchol(13,None,Vrchol(5,Vrchol(8))),Vrchol(2,Vrchol(11,Vrchol(19)),Vrchol(3)))
>>> pocet(strom)
    8
>>> pocet_listov(strom)
    3
>>> strom = Vrchol(1, Vrchol(2, Vrchol(3, Vrchol(4, Vrchol(5)))))
>>> pocet_listov(strom)
    1
```

Pre triedu Vrchol otestuj magickú metódu __repr__() z prednášky na niektorých stromoch z predchádzajúcich úloh. Trieda Vrchol s metódou __repr__():

class Vrchol:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

    def __repr__(self):
        return f'Vrchol({self.data!r}, {self.left}, {self.right})'

Napríklad:

>>> t = Vrchol(1, Vrchol(2, None, Vrchol(5, Vrchol(6), Vrchol(7))), Vrchol(3, Vrchol(4)))
>>> t
    Vrchol(1, Vrchol(2, None, Vrchol(5, Vrchol(6, None, None), Vrchol(7, None, None))),
    Vrchol(3, Vrchol(4, None, None), None))

Teraz uprav túto metódu tak, aby sa listy stromu nevypisovali v tvare 'Vrchol(hodnota, None, None)', ale ako 'Vrchol(hodnota)' (bez dvoch zbytočných None) a tiež aj vrcholy, ktoré majú pravý podstrom None sa vypíšu bez tohto parametra. Napríklad:

>>> s = Vrchol('a', Vrchol('b', right=Vrchol('c')), Vrchol('d', Vrchol('f'), Vrchol('e')))
>>> s
    Vrchol('a', Vrchol('b', None, Vrchol('c')), Vrchol('d', Vrchol('f'), Vrchol('e')))
>>> Vrchol('a', Vrchol('a', Vrchol('a')), Vrchol('a', Vrchol('a')))
    Vrchol('a', Vrchol('a', Vrchol('a')), Vrchol('a', Vrchol('a')))

Nakresli všetky rôzne binárne stromy, ktoré sa skladajú z 3 vrcholov s hodnotami 'x'. Týchto stromov by malo byť 5. Nakresli ich všetky vedľa seba (pomocou kresli()) do jednej grafickej plochy (do jedného canvas príde 5 volaní kresli), napríklad takto:
```
kresli(Vrchol('x', Vrchol('x'), Vrchol('x')), 50, 50, 30)
kresli(Vrchol('x', Vrchol('x', Vrchol('x'))), 50, 150, 30)
...
```
Pokús sa odhadnúť, koľko existuje rôznych binárnych stromov, ktoré sú zložené zo štyroch vrcholov.

Ručne zisti, čo vypíše upravená funkcia vypis:

def vypis(vrch, k=0):
    if vrch is None:
        print('.' * k, None)
        return
    print('.' * k, vrch.data)
    vypis(vrch.left, k + 2)
    vypis(vrch.right, k + 2)

vypis(Vrchol('koren', Vrchol('lavy'), Vrchol('pravy')))

Skús aj:

vypis(Vrchol('A', Vrchol('B', None, Vrchol('D')), Vrchol('C', Vrchol('E'))))

Napíš funkciu pocet2(vrch), ktorá vráti počet vrcholov v strome, ktoré majú práve 2 potomkov. Funkciu otestuj aj na väčšom strome, ktorý vygeneruješ náhodne:
```
def pocet2(vrch):
    ...
```
Napríklad:
```
strom = vyrob_strom(range(30))
kresli(strom, ...)
print('pocet2 =', pocet2(strom))
```

Napíš funkciu nachadza_sa(vrch, hodnota), ktorá zistí (vráti True alebo False), či sa v strome nachádza daná hodnota. Funkcia bude zrejme rekurzívna:

def nachadza_sa(vrch, hodnota):
    ...

Napríklad:

strom = vyrob_strom(range(1, 30, 3))
kresli(strom, ...)
for i in range(30):
    print(i, 'sa nachadza', nachadza_sa(strom, i))

Napíš funkciu pocet_vyskytov(vrch, hodnota), ktorá zistí počet výskytov danej hodnoty v strome. Budeš to riešiť zrejme rekurzívne:

def pocet_vyskytov(vrch, hodnota):
    ...

Napríklad:

strom = vyrob_strom('abcabcababcabacaba')
kresli(strom, ...)
for i in 'abcd':
    print(i, 'pocet vyskytov', pocet_vyskytov(strom, i))

Napíš funkciu min_max(vrch), ktorá vráti dvojicu (tuple) s minimálnou a maximálnou hodnotou v strome:
```
def min_max(vrch):
    ...
```
Napríklad:
```
>>> print(min_max(Vrchol(5, Vrchol(7), Vrchol(2))))
    (2, 7)
```

Napíš funkciu vytvor_uplny(n), ktorá vráti vygenerovaný úplný strom: jeho najvyššia úroveň je n a hodnoty vo všetkých vrcholoch nech sú 0. Zrejme použiješ rekurziu: úplný strom úrovne n sa skladá z ľavého úplného stromu úrovne n-1, z pravého úplného stromu tiež úrovne n-1 a z koreňa, ktorý má tieto dva podstromy:
```
def vytvor_uplny(n):
    ...
```
Otestuj pre rôzne n, napríklad:
```
strom = vytvor_uplny(5)
kresli(strom, ...)
```

Napíš funkciu mapuj(vrch, funkcia), ktorá zmení hodnoty vo všetkých vrcholoch stromu aplikovaním danej funkcie, t.j. pre každý vrchol zoberie hodnotu, zavolá s ňou danú funkciu a túto novú vypočítanú hodnotu vráti do vrcholu:
```
def mapuj(vrch, funkcia):
      ...
```
Otestuj, čo urobí so stromom takáto funkcia?
```
p = 0
def fun(h):
    global p
    p += 1
    return p
```

Napíš funkcie daj_zoznam(vrch) a daj_mnozinu(vrch), ktoré vrátia buď zoznam, alebo množinu všetkých hodnôt v strome. Tieto dve funkcie sa možno budú trochu podobať na funkciu sucet() z prednášky:
```
def daj_zoznam(vrch):
    ...

def daj_mnozinu(vrch):
    ...
```

5. Týždenný projekt¶

Úlohou je vytvoriť súbor riesenie.py, ktorý implementuje funkcie add_node(), create_tree(), write_tree_to_file, most_frequent a number():

class Node:
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

def add_node(root, string):
    ...

def create_tree(file_name):
    ...

def write_tree_to_file(root, file_name):
    ...

def most_frequent(root):
    ...

def number(root):
    ...

Triedu Node nemodifikuj a nedefinuj žiadne iné triedy.

Funkcie¶

add_node(root, string)¶

Táto funkcia dostane ako vstup koreň stromu a reťazec.

root je buď existujúca inštancia triedy Node, alebo None
string je ľubovoľný reťazec vo formáte 'meno:cesta'

Funkcia má rozšíriť binárny strom zadaný koreňom o nový vrchol a potom vrátiť tento strom ako výsledok funkcie. Hodnotou nového vrcholu (atribút data) je prvé slovo daného reťazca. Miesto, kde sa má nový vrchol pripojiť, je definované postupnosťou (reťazcom cesta), z ktorej nás budú zaujímať len písmená 'l' a 'r' (môžu byť aj veľké 'L' a 'R'). Začína sa od koreňa stromu. Pri písmene 'l' sa pokračuje doľava a pri písmene 'r' sa pokračuje doprava. Iné znaky ako písmená 'l' a 'r' sa ignorujú. Napríklad reťazec 'meno: vpravo a VLAVO' označuje meno vrcholu 'meno' a z cesty sa použijú len znaky najprv 'r' a potom 'L', ostatné sa odignorujú.

Cesta teda vedie

buď k už existujúcemu vrcholu - vtedy sa hodnota tohto existujúceho vrcholu nahradí novým menom, nič iné v strome sa nezmení
alebo k novému vrcholu, ktorý sa vytvorí aj s novou hodnotou vo vrchole; ak na ceste k tomuto vrcholu nejaký vrchol ešte neexistoval, tak sa vytvorí s hodnotou None

Ak cesta neexistuje (parameter string neobsahuje ':' alebo znak ':' je posledným znakom reťazca), nastavuje sa nová hodnota do koreňa stromu.

Funkcia vždy vráti referenciu na koreň stromu (ak parameter node nebol pri volaní funkcie None, návratovou hodnotou bude tento pôvodný koreň stromu).

Príklad:

root = None
root = add_node(root, 'KING')                     # Node('KING')
root = add_node(root, 'QUEEN:L')                  # Node('KING', Node('QUEEN'))
root = add_node(root, 'PRINCE: L L L')            # Node('KING', Node('QUEEN', Node(None, Node('PRINCE'))))
root = add_node(root, 'FROG:w h y a m i f r o g') # Node('KING', Node('QUEEN', Node(None, Node('PRINCE'))), Node('FROG'))

create_tree(file_name)¶

Táto funkcia dostane ako vstup file_name: textový súbor má riadky vo formáte ako bol reťazec string z funkcie add_node(). Tvojou úlohou je tento súbor spracovať a podľa riadkov v ňom vytvoriť a vrátiť nový strom (teda vráti koreň takto vytvoreného binárneho stromu).

write_tree_to_file(root, file_name)¶

Táto funkcia robí presný opak oproti funkcii create_tree(). Na vstupe dostane root (inštancia triedy Node) a file_name (reťazec s cestou k súboru). Úlohou funkcie je vytvoriť textový súbor, ktorý reprezentuje daný strom zadaný referenciou na koreň. (Pomocou takto zapísaného súboru by sa mal dať vytvoriť identický strom volaním funkcie create_tree())

most_frequent(root)¶

Táto funkcia dostane ako parameter root referenciu na koreň stromu. Funkcia vráti znakový reťazec, ktorý sa v strome vyskytol najviackrát ako hodnota vo vrchole (meno vrcholu). Ak je tekých reťazcov viac, funkcia vráti ľubovoľný z nich. Pre prázdny strom vráti None.

number(root)¶

Táto funkcia dostane ako parameter root referenciu na koreň stromu. Funkcia vráti dvojicu čísel (tuple): počet vrcholov stromu, ktoré nemajú v atribúte data hodnotu None a počet všetkých vrcholov stromu.

Obmedzenia¶

riešenie odovzdaj v súbore riesenie.py, pričom sa v ňom bude nachádzať len jedna definícia triedy Node a týchto 5 funkcií: add_node, write_tree_to_file, create_tree, most_frequent a number

prvé tri riadky tohto súboru budú obsahovať:

# 5. zadanie: binarny strom
# autor: Janko Hrasko
# datum: 21.3.2023

zrejme ako autora uvedieš svoje meno
tvoj program by nemal počas testovania testovačom nič vypisovať (žiadne testovacie print())

Testovanie¶

Keď budeš spúšťať svoje riešenie na počítači, môžeš do súboru riesenie.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napríklad:

if __name__ == '__main__':
    s = add_node(None, 'a:rxl l')
    s = add_node(s, 'b:rl')
    s = add_node(s, 'c:LL')
    write_tree_to_file(s, 'strom1.txt')
    t = create_tree('strom1.txt')
    print(number(t))
    t = add_node(t, 'x')
    t = add_node(t, 'd:' + 'lr'*10)
    write_tree_to_file(t, 'strom2.txt')
    print('subor strom1.txt')
    print(open('strom1.txt').read())
    print('subor strom2.txt')
    print(open('strom2.txt').read())

Tento test by mal vypísať:

(3, 6)
subor strom1.txt
c:ll
b:rl
a:rll

subor strom2.txt
a:rll
d:lrlrlrlrlrlrlrlrlrlr
c:ll
x
b:rl

Uvedom si, že poradie riadkov v týchto súboroch môže byť ľubovoľne iné.

Súbor riesenie.py odovzdaj na úlohový server https://list.fmph.uniba.sk/.

5. Binárne stromy¶

Všeobecný strom¶

Binárny strom¶

Realizácia spájanou štruktúrou¶

Nakreslenie stromu¶

Generovanie náhodného stromu¶

Ďalšie rekurzívne funkcie¶

Metóda __repr__¶

Cvičenia¶

5. Týždenný projekt¶

Funkcie¶

add_node(root, string)¶

create_tree(file_name)¶

write_tree_to_file(root, file_name)¶

most_frequent(root)¶

number(root)¶

Obmedzenia¶

Testovanie¶

Metóda repr¶