28. Binárne stromy

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

  • rodokmeň, napr. potomkovia anglickej kráľovnej Alžbety II:

    • z tabuľky potomkov na wikipédii môžeme pripraviť takéto grafické zobrazenie:

      potomkovia anglickej kráľovnej
    • 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.) práve dvoch rodičov: otec je horná osoba a matka je dolná

  • štruktúra adresárov 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á z troch sekcií (matematickej, fyzikálnej a informatickej) 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 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. v prednáške 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, v ktorá má nejaký počiatočný vrchol (napr. 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, …).

28.1. 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 (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 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. A, B, L sú súrodenci, ale I a M nie sú

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

  • okrem listov sú v strome 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. 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. 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, alebo
  • obsahuje koreň a množinu podstromov, ktoré vychádzajú z tohto koreňa, pričom každý podstrom je opäť všeobecný strom (má svoj koreň a svoje podstromy)

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

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

28.2.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 definujeme 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 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. 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 zautomatizovať. Napr. pre 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.

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

kresli(strom, 200, 200, 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. 40
  • smerom vpravo budeme kresliť pravý podstrom a teda x-ovú súradnicu zväčšíme tak, aby bola v polovici šírky oblasti

Ak chceme kresliť aj hrany stromu (spojnice medzi vrcholmi), zapíšeme to napr. takto (táto druhá verzia má ešte chyby):

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

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:

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

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

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

  • 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

28.2.3. Generovanie nahodné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 rr(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. 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):
from random import randrange as rr

def pridaj_vrchol(vrch, hodnota):
    while True:
        if rr(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

alebo rekurzívna verzia:

def pridaj_vrchol(vrch, hodnota):
    if rr(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(rr(20))
for h in range(20):
    pridaj_vrchol(koren, rr(20))

28.2.4. Ďalšie rekurzívne funkcie

Tieto funkcie postupne (rekurzívne) prechádzajú 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ýsledok 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 to zapisujú aj takto „úspornejšie“:

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

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 =', pocet(koren))

Ďalej budeme zisťovať výšku stromu (opäť bude niekoľko verzií). Najprv verzia, ktorá ešte nie je 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. Inak sa vypočíta výška ľavého podstromu, potom výška pravého a na záver sa z týchto dvoch výšok vyberie ta 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.

>>> 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 2 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(koren))

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

Vo výpise sa objavia všetky hodnoty vo vrchol v nejakom poradí.

28.2.5. Metóda __repr__

Veľmi zaujímavo sa správa metóda __repr__() 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 'Vrchol({}, {}, {})'.format(self.data, 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 zvláda aj triviálny prípad.

28.3. Cvičenie

Na riešenie úloh si z prednášky okopírujte definíciu triedy Vrchol a tiež niektoré funkcie, ktoré môžete využiť v úlohách.

  1. Do premennej strom sme priradili binárny strom
  • nakreslite ho na papier (bez počítača)
>>> strom = Vrchol(7,Vrchol(13,None,Vrchol(5,Vrchol(8))),Vrchol(2,Vrchol(11,Vrchol(19)),Vrchol(3)))
  • skontrolujte vašu kresbu s vykreslením pomocou kresli()
  1. Na papier nakreslite taký binárny strom, ktorý má 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 '.'.
  • vytvorte tento strom pomocou priradenia (alebo aj viacerých priradení)
strom = Vrchol(...)
  • nakreslite tento strom pomocou kresli()
  1. Napíšte funkciu sest_listov(slovo), ktorá vytvorí binárny strom so šiestimi listami podobne ako v úlohe (2), ale hodnotami v listoch budú písmená z daného slova
  • otestujte napr.
strom = sest_listov('pascal')
kresli(...)
  1. Upravte metódu __repr__() z prednášky tak, aby sa listy stromu nevypisovali v tvare 'Vrchol(hodnota, None, None)', ale ako 'Vrchol(hodnota)'. Tiež opravte túto metódu tak, aby sa napr. reťazce ako hodnoty vypísali aj s apostrofmi (dátová časť vrcholu sa musí vypísať ako repr())
  • napr.
>>> s = Vrchol(11, Vrchol(22, Vrchol(44)), Vrchol(33, right=Vrchol(55)))
>>> s
Vrchol(11, Vrchol(22, Vrchol(44), None), Vrchol(33, None, Vrchol(55)))
>>> Vrchol('P', Vrchol('y'), Vrchol('t'))
Vrchol('P', Vrchol('y'), Vrchol('t'))
  1. Na papier nakreslite také binárne stromy, ktoré majú 6 vrcholov (hodnoty vo vrcholoch nás teraz nezaujímajú) ale
  • majú len 1 list
  • majú 2 listy, ale maximálnu možnú výšku
  • majú 2 listy, ale minimálnu možnú výšku
  • majú maximálny možný počet listov

Tieto stromy môžete aj zadefinovať ako pythonovskú štruktúru strom a vykresliť pomocou kresli()

  1. Na papier nakreslite všetky rôzne binárne stromy, ktoré majú 3 vrcholy s hodnotami vo vrcholoch ' ':
  • malo by ich byť 5
  • aspoň tri z nich nakreslite (pomocou kresli()) do grafickej plochy vedľa seba
  1. Ručne zistite, čo sa vypíše
  • upravená funkcia vypis:
def vypis(vrch, k):
    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')), 0)
  1. Napíšte funkciu pocet_listov(vrch), ktorá vráti počet listov v strome
  • funkcia bude 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íte počet listov v ľavom podstrome a aj počet listov v pravom podstrome, tieto dva výsledky spočítate a tento súčet je výsledným počtom listov v celom strome
  • funkciu otestujte, napr.
>>> strom = Vrchol('X',Vrchol('Y'),Vrchol('Z'))
>>> pocet_listov(strom)
2
>>> pocet_listov(Vrchol('X',Vrchol('Y',Vrchol('Z',Vrchol('U')))))
1
  1. Napíšte funkciu pocet2(vrch), ktorá vráti počet vrcholov v strome, ktoré majú práve 2 synov
  • funkciu otestujte aj na väčšom strome, ktorý vygenerujete náhodne
def pocet2(vrch):
    ...
  1. Pozmeňte funkciu kresli(...) tak, aby bol koreň pri vykreslení zafarbený na červeno, všetky listy na modro a zvyšné vrcholy ostanú biele
  • do funkcie môžete pridať ďalší parameter, napr.
def kresli(vrch, sir, x, y, koren=True):
    ...
  1. Napíšte funkciu nachadza_sa(vrch, hodnota), ktorá zistí (vráti, True alebo False), či sa v strome nachádza daná hodnota
  • riešite zrejme rekurzívne:
def nachadza_sa(vrch, hodnota):
    ...
  1. Napíšte funkciu pocet_vyskytov(vrch, hodnota), ktorá zistí počet výskytov danej hodnoty v strome
  • riešite zrejme rekurzívne:
def pocet_vyskytov(vrch, hodnota):
    ...
  1. Napíšte funkciu min_max(vrch), ktorá vráti dvojicu (tuple) s minimálnou a maximálnou hodnotou v strome
  • napr.
def min_max(vrch):
    ...

print(min_max(Vrchol(5, Vrchol(7), Vrchol(2))))

(2, 7)
  1. Napíšte funkciu strom1(n), ktorá vygeneruje strom s n vrcholmi, pričom každý z nich, okrem posledného, má práve jedného syna, hodnoty vo vrcholoch sú postupne 0, 1, 2, …, n-1. Koreň stromu má iba ľavého syna, tento má iba pravého, ďalší má opäť iba ľavého, atď. Uvedomte si, že funkcia musí vrátiť referenciu na koreň stromu ako svoj výsledok.
  • riešte najprv pomocou rekurzie - môžete použiť aj ďalšie parametre s náhradnou hodnotou, napr.
def strom1(n, vlavo=True):    # alebo def strom1(n, hodnota=0):
    ...
  • riešte aj bez rekurzie
def strom1(n):
    ...
  1. Napíšte funkciu strom2(n), ktorá vygeneruje strom s výškou n, pričom koreň má 2 synov (alebo žiadneho pre n = 0), ľavý podstrom má synov iba vľavo a pravý podstrom má všetky vrcholy iba vpravo. Vrcholy majú hodnoty podľa úrovne: koreň 0, jeho synovia 1, ich synovia 2, atď. Uvedomte si, že funkcia musí vrátiť referenciu na koreň stromu ako svoj výsledok.
  • riešte bez rekurzie

    def strom2(n):
        ...
    
  1. Napíšte 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žijete 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):
    ...
  1. Napíšte 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):
        ...
    
  1. Napíšte funkcie daj_pole(vrch) a daj_mnozinu(vrch), ktoré vrátia buď pole, alebo množinu všetkých hodnôt v strome
  • def daj_pole(vrch):
        ...
    
    def daj_mnozinu(vrch):
        ...
    

28.4. Domáce zadanie

Vašou úlohou je vytvoriť súbor uloha5.py, ktorý implementuje funkcie pridaj_vrchol(), vytvor_strom() a zapis_strom_do_suboru():

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

Triedu Vrchol nemodifikujte a nedefinujte žiadne iné triedy.

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 ľubovolný string vo formáte 'meno x y ...'

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ťazcov {'L', 'R'} (môžu to byť aj malé písmená 'l', 'r'). Začína sa od koreňa stromu. Pri písmene 'L' (jednoznakovom reťazci) sa pokračuje doľava a pri písmene 'R' sa pokračuje doprava. Iné reťazce ako písmená 'L' a 'R' sa ignorujú. Napr. reťazec 'meno r rr l, m left L' označuje meno vrcholu 'meno' a z cesty sa použijú len reťazce prvé 'r' a posledné 'L', ostatné sa odignorujú.

Cesta teda vedie

  • buď k už existujúcemu vrcholu - vtedy sa tento existujúci vrchol nahradí novovytvoreným vrcholom, ak z pôvodného vrcholu vychádzali nejaké hrany, tak tieto sa stratia, teda nový vrchol nahradí celý podstrom,
  • alebo k novému synovi existujúceho vrcholu - nový vrchol sa pripojí ako nový syn existujúceho vrcholu
  • ak cesta nevedie nikam - neexistuje taký vrchol nie je to ani syn existujúceho vrcholu, funkcia pridaj_vrchol() nespraví nič, teda iba vráti referenciu na pôvodný strom

Jedinou výnimkou je, keď koreň je None a reťazec obsahuje iba meno. Vtedy sa vytvorí nový vrchol a ten sa stane koreňom stromu (a funkcia ho vráti ako svoj výsledok).

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 L') # Vrchol(KING, Vrchol(QUEEN))
vrchol = pridaj_vrchol(vrchol, 'FROG w h y a m i f r o g :(') # Vrchol(KING, Vrchol(QUEEN), Vrchol(FROG))

vytvor_strom()

Táto funkcia dostane ako vstup meno súboru (teda reťazec s cestou k súboru). Súbor má riadky vo formáte ako bol reťazec z funkcie pridaj_vrchol(). Vašou ú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ť 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())

Príklad:

pre súbor 'try1.txt':

A
B L
C R
D L L
E L R
F R L

a 'try2.txt':

A
B - - - L - - - - -
Z L L L
C R
D L L
E L R
R R R R
F R L

tento program:

strom1 = vytvor_strom('try1.txt')
strom2 = vytvor_strom('try2.txt')

vytvorí stromy strom1 a strom2 a oba vyzerajú takto:

  A
 +--+
 B  C
+-+ +
D E F

a tiež zapis_strom_do_suboru(strom1, 'output.txt') vyprodukuje 'output.txt', ktorý môže ale nemusí vyzerať takto:

A
B L
C R
D L L
E L R
F R L