28. 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 anglickej kráľovnej Alžbety II:

    • z tabuľky potomkov na wikipédii môžeme pripraviť takéto grafické zobrazenie (obrázok je zo začiatku 2019):

      potomkovia anglickej kráľovnej

      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

      predkovia anglickej kráľovnej

      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 47 sú štyria starí rodičia súčasnej kráľovnej; osoby s číslami 815 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 sekcií (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:

všeobecný strom

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 otec, resp. rodič, predok (ancestor, parent)

  • nasledovník vrcholu sa nazýva syn, resp. dieťa alebo potomok (child, descendant)

  • vrcholy, ktoré majú spoločného predchodcu (otca) sa nazývajú súrodenci (siblings), napríklad A, B, L sú súrodenci, ale I a M 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 otcom a synom 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 synovia majú hĺbku 1, ich synovia (vnuci) 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 synov, 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 synom - budeme to kresliť buď šípkou šikmo vľavo dole alebo šikmo vpravo dole

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

binárny strom

Vrchol b nemá ľavého syna, len pravého. Rovnako je na tom aj vrchol e. Vrchol f má len ľavého syna a nemá pravého. Všetky ostatné vrcholy sú buď listami (nemajú žiadneho syna) alebo majú oboch synov, ľ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á otcov a synov, 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 synov, teda v 1. úrovni môžu byť maximálne 2 vrcholy

  • v 2. úrovni môžu byť len synovia 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:

úplný binárny strom

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 None:
        return
    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 synov, 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

L.I.S.T.


  1. 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 = data
            self.left = left
            self.right = 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(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')
    

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

    _images/28_6.png

    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


  1. Nakresli aj tento strom a zisti, aká je jeho výška:

    _images/28_7.png
    • skontroluj pomocou funkcie vyska()

    • aká je šírka tohto stromu (zatiaľ bez funkcie)?


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

    _images/28_8.png

  1. Na papier 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 '.'. Priraď tento strom do premennej a skontroluj:

    strom = ...
    kresli(strom, ...)
    
    • Navrhni taký strom, 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.


  1. Na papier nakresli také binárne stromy, ktoré majú presne 6 vrcholov (hodnoty vo vrcholoch nás teraz nezaujímajú, môžu to byť medzery), 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

    Aj tieto štyri stromy zadefinuj ako pythonovskú štruktúru strom a vykresliť pomocou kresli().


  1. 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 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.


  1. Napíš funkciu pocet_listov(vrch), ktorá pre daný binárny strom zistí počet listov. Funkcia sa bude podobať funkcii pocet(strom). 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
    

  1. 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')))
    

  1. Na papier 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)
    ...
    

    Vedel by si odhadnúť, koľko existuje rôznych binárnych stromov, ktoré sú zložené zo štyroch vrcholov?


  1. 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'))))
    

  1. Napíš funkciu pocet2(vrch), ktorá vráti počet vrcholov v strome, ktoré majú práve 2 synov. 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))
    

  1. Napíš funkciu nachadza_sa(vrch, hodnota), ktorá zistí (vráti True alebo False), či sa v strome nachádza daná hodnota. Budeš to riešiť zrejme rekurzívne:

    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))
    

  1. 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))
    

  1. 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)
    

  1. 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, ...)
    

  1. 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
    

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

    def daj_pole(vrch):
        ...
    
    def daj_mnozinu(vrch):
        ...
    

5. Domáce zadanie

L.I.S.T.


Úlohou je vytvoriť súbor riesenie.py, ktorý implementuje funkcie pridaj_vrchol(), vytvor_strom(), zapis_strom_do_suboru() a pocet():

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

def pridaj_vrchol(koren, riadok):
    ...

def vytvor_strom(meno_suboru):
    ...

def zapis_strom_do_suboru(koren, meno_suboru):
    ...

def pocet(koren):
    ...

Triedu Vrchol nemodifikuj a nedefinuj žiadne iné triedy.

Funkcie

pridaj_vrchol()

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

  • koreň je buď existujúca inštancia triedy Vrchol, alebo None

  • reťazec je ľubovoľný string 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 riadok 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 koren nebol pri volaní funkcie None, návratovou hodnotou bude tento pôvodný koreň stromu).

Príklad:

vrchol = None
vrchol = pridaj_vrchol(vrchol, 'KING') # Vrchol('KING')
vrchol = pridaj_vrchol(vrchol, 'QUEEN:L') # Vrchol('KING', Vrchol('QUEEN'))
vrchol = pridaj_vrchol(vrchol, 'PRINCE: L L L') # Vrchol('KING', Vrchol('QUEEN', Vrchol(None, Vrchol('PRINCE'))))
vrchol = pridaj_vrchol(vrchol, 'FROG:w h y a m i f r o g') # Vrchol('KING', Vrchol('QUEEN', Vrchol(None, Vrchol('PRINCE'))), Vrchol('FROG'))

vytvor_strom()

Táto funkcia dostane ako vstup meno súboru. Textový súbor má riadky vo formáte ako bol reťazec riadok z funkcie pridaj_vrchol(). 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).

zapis_strom_do_suboru()

Táto funkcia robí presný opak oproti funkcii vytvor_strom(). Na vstupe dostane koreň (inštancia triedy Vrchol) a meno súboru (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 vytvor_strom())

pocet()

Táto funkcia dostane ako parameter koren 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 Vrchol a 4 funkcie pridaj_vrchol, zapis_strom_do_suboru, vytvor_strom a pocet

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

    # 5. zadanie: binarny strom
    # autor: Janko Hrasko
    # datum: 30.3.2020
    
  • 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 = pridaj_vrchol(None, 'a:rxl l')
    s = pridaj_vrchol(s, 'b:rl')
    s = pridaj_vrchol(s, 'c:LL')
    zapis_strom_do_suboru(s, 'strom1.txt')
    t = vytvor_strom('strom1.txt')
    print(pocet(t))
    t = pridaj_vrchol(t, 'x')
    t = pridaj_vrchol(t, 'd:' + 'lr'*10)
    zapis_strom_do_suboru(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 odovzdávaj na úlohový server https://list.fmph.uniba.sk/ najneskôr 10. apríla do 23:00. Za toto riešenie môžeš získať 10 bodov.