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á v zozname svojho predchodcu - už vieme, že keď chceme zrušiť zo zoznamu nejaký vrchol, musíme meniť 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. 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 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, 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, …).

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

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

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

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

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

alebo 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.randrange(20))
for h in range(20):
    pridaj_vrchol(koren, random.randrange(20))

alebo:

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

Ď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í.

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 f'Vrchol({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.



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

      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 C 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 C do listov stromu


  1. Aj pre tento strom 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. 'lightgreen') ako vnútorné vrcholy (napr. 'lightblue'). Napr.

    _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 (napr. vrchol 'P' bude mať vzdialenosť 1, vrchol 'y' vzdialenosť 2, vrchol 't' vzdialenosť 3, …). Priraď tento strom do premennej a nakresli.


  1. Napíš funkciu vyrob_strom(postupnost), ktorá vytvorí náhodný binárny strom z prvkov zadanej 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. 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 volanie vyrob_strom(range(1000)) a vypíš výšku tohto stromu aj počet vrcholov


  1. Napíš funkciu pocet_listov(vrch), ktorá pre daný binárny strom zistí počet listov. Funkcia sa bude podobať funkcii pocet(vrch).

    • 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í 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.

      >>> 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}, {self.left}, {self.right})'
      
    • napr.

      >>> 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 . Tiež oprav túto metódu tak, aby sa reťazce ako hodnoty vypísali aj s apostrofmi

    • napr.

      >>> 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':

    • malo by ich 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.

      canvas = tkinter.Canvas(width=510, height=200)
      canvas.pack()
      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 sa 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. Pozmeň funkciu kresli(...) tak, aby bol koreň pri vykreslení zafarbený na červeno, všetky listy na bledozeleno a zvyšné vrcholy na bledomodro.

    • do funkcie môžeš pridať ďalší parameter, napr.

      def kresli(vrch, sir, x, y, koren=True):
          ...
      

  1. Napíš 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ý vygeneruješ náhodne

      def pocet2(vrch):
          ...
      

  1. Napíš funkciu nachadza_sa(vrch, hodnota), ktorá zistí (vráti, True alebo False), či sa v strome nachádza daná hodnota

    • budeš riešiť zrejme rekurzívne:

      def nachadza_sa(vrch, hodnota):
          ...
      

  1. Napíš funkciu pocet_vyskytov(vrch, hodnota), ktorá zistí počet výskytov danej hodnoty v strome

    • budeš riešiť zrejme rekurzívne:

      def pocet_vyskytov(vrch, hodnota):
          ...
      

  1. Napíš 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íš 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):
          ...
      

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

  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.

Vašou úlohou je vytvoriť súbor riesenie5.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 nemodifikujte a nedefinujte ž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. 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 (teda reťazec s cestou k súboru). Súbor má riadky vo formáte ako bol reťazec riadok 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())

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

  • vaše riešenie odovzdajte v súbore riesenie5.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: 22.3.2019
    
  • zrejme ako autora uvediete svoje meno

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

Testovanie

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

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 vám 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

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

Súbor riesenie5.py odovzdávajte na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 2. apríla. Za toto riešenie môžete získať 10 bodov.