29. Trieda BinarnyStrom

Doteraz sme pracovali so stromom tak, že sme zadefinovali triedu Vrchol pre jeden vrchol stromu a k tomu sme zadefinovali niekoľko funkcií (väčšinou rekurzívnych), ktoré s pracovali s celým stromom. Napr.

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

koren = Vrchol(...)
vypis(koren)

Vypíše všetky hodnoty vo vrchol stromu v nejakom poradí.

Prirodzenejšie a programátorsky správnejšie by bolo zadefinovanie triedy Strom, ktorá okrem definície jedného vrcholu bude obsahovať aj všetky užitočné funkcie ako svoje metódy. Teda zapuzdrime všetky funkcie spolu s dátovou štruktúrou do jedného „obalu“. Pre prístup ku stromu (k jeho vrcholom) si musíme pamätať referenciu na jeho koreň - to bude atribút self.root, ktorý bude mať pri inicializácii hodnotu None. Zapíšme základ:

class BinarnyStrom:

    #------ vnorena trieda ------

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

    #------ koniec definicie vnorenej triedy ------

    def __init__(self):
        self.root = None

Takto sme na minulej prednáške pridávali nový vrchol na náhodnú pozíciu v strome:

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

Museli sme pritom predpokladať, že koreň stromu už existuje a jeho referencia je prvým parametrom funkcie. Z tejto funkcie urobíme metódu, ktorá bude fungovať aj pre prázdny strom. Zároveň doplníme inicializáciu __init__() o jeden parameter, vďaka čomu sa môže už pri inicializácii inštancie vytvoriť strom s náhodným umiestnením vrcholov s danými hodnotami:

from random import randrange as rr

class BinarnyStrom:

    #------ vnorena trieda ------

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

    #------ koniec definicie vnorenej triedy ------

    def __init__(self, pole=None):
        self.root = None
        if pole is not None:
            for hodnota in pole:
                self.pridaj_vrchol(hodnota)

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

Takto vieme vytvárať náhodné binárne stromy s rôznym počtom vrcholov, ale zatiaľ s takýmito stromami nevieme robiť vôbec nič. Napr.

s1 = BinarnyStrom('Python')
s2 = BinarnyStrom([1]*100)
s3 = BinarnyStrom(x**2 for x in range(10))

Ďalšou veľmi užitočnou funkciou pre binárny strom bola kresli():

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

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

strom = Vrchol(...)
kresli(strom, 200, 200, 40)

V tomto prípade bude treba riešiť niekoľko komplikácií:

  1. funkcia kresli() je rekurzívna, takže sa nebude dať priamo prerobiť na metódu tak, ako sme to urobili pre pridaj_vrchol()
  2. canvas je tu globálna premenná, hoci nám by sa asi viac hodil triedny atribút, ktorý by bol spoločný pre všetky inštancie
  3. canvas by bolo vhodné inicializovať až pri prvom zavolaní metódy kresli() (zrejme to nesmieme inicializovať ako self.canvas=tkinter.Canvas(...))
  4. strom sa bude automaticky kresliť hore v strede grafickej plochy, preto bude treba predchádzajúcu kresbu v grafickej ploche vymazať, napr. pomocou canvas.delete('all')

Teraz to už môžeme zapísať kompletné:

from random import randrange as rr
import tkinter

class BinarnyStrom:

    canvas = None
    sirka0, vyska0 = 800, 400

    #------ vnorena trieda ------

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

    #------ koniec definicie vnorenej triedy ------

    def __init__(self, pole=None):
        self.root = None
        if pole is not None:
            for hodnota in pole:
                self.pridaj_vrchol(hodnota)

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

    def kresli(self):

        #---- vnorena rekurzivna funkcia ----

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

        #----

        if self.canvas is None:
            BinarnyStrom.canvas = tkinter.Canvas(width=self.sirka0, height=self.vyska0)
            self.canvas.pack()
        self.canvas.delete('all')
        kresli_rek(self.root, self.sirka0/2-20, self.sirka0/2, 40)

Všimnite si, ako sme to vyriešili:

  1. pôvodnú rekurzívnu funkciu sme premenovali na kresli_rek() a vnorili sme ju do metódy kresli() (tá je teraz bez parametrov)
  2. canvas je teraz triedny atribút, inicializovaný je hodnotou None, okrem toho sme zadefinovali ešte dva takéto atribúty sirka0 a vyska0, v ktorých je nastavená veľkosť grafickej plochy
  3. pri prvom zavolaní metódy kresli() má atribút canvas zatiaľ hodnotu None, preto treba vytvoriť grafickú plochu BinarnyStrom.canvas = tkinter.Canvas(...)
  4. pre každým vykresľovaním do grafickej plochy sa najprv táto vymaže pomocou canvas.delete('all')

Môžeme otestovať:

>>> s = BinarnyStrom('abcdefghijkl')
>>> s.kresli()

Dostávame napr.:

binárny strom

Na minulej prednáške sme zostavili niekoľko ďalších funkcií, napr. aj tú, ktorá počíta počet prvkov (vrcholov) stromu:

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

Keďže táto funkcia očakáva ako vstup vrchol, od ktorého sa počíta počet vrcholov (podstromu), musíme aj metódu, ktorá zisťuje počet prvkov, napr. __len__(), zapísať inak. Môžeme túto globálnu funkciu volať z metódy v triede:

class BinarnyStrom:

    ...

    def __len__(self):
        return pocet(self.root)

Toto je ale veľmi nevhodný spôsob, lebo okrem triedy sa musíme starať aj o nejakú globálnu funkciu - prípadne ich potom neskôr bude aj viac takýchto podobných. Všetky pomocné funkcie by mali byť tiež zapuzdrené v triede, najlepšie ako vnorené funkcie tam, kde sa budú používať. Opäť to urobíme podobne ako s metódou kresli():

class BinarnyStrom:

    ...

    def __len__(self):
        #---- vnorena rekurzivna funkcia ----
        def pocet(vrch):
            if vrch is None:
                return 0
            return 1 + pocet(vrch.left) + pocet(vrch.right)
        #----
        return pocet(self.root)

Takýmto zápisom sa funkcia pocet() stáva lokálnou (vnorenou) do metódy __len__() a nik okrem nej ju nemôže používať. Takto to budeme najčastejšie používať pri všetkých rekurzívnych funkciách. Prepíšme niektoré ďalšie funkcie ako metódy tejto triedy:

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

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

def nachadza_sa(vrch, hodnota):
    if vrch is None:
        return False
    if vrch.data == hodnota:
        return True
    if nachadza_sa(vrch.left, hodnota):
        return True
    if nachadza_sa(vrch.right, hodnota):
        return True
    return False

Ako metódy:

class BinarnyStrom:

    ...

    def sucet(self):
        #---- vnorena rekurzivna funkcia ----
        def sucet_rek(vrch):
            if vrch is None:
                return 0
            return vrch.data + sucet_rek(vrch.left) + sucet_rek(vrch.right)
        #----
        return sucet_rek(self.root)

    def vyska(self):
        #---- vnorena rekurzivna funkcia ----
        def vyska_rek(vrch):
            if vrch is None:
                return -1
            return 1 + max(vyska_rek(vrch.left), vyska_rek(vrch.right))
        #----
        return vyska_rek(self.root)

    def __contains__(self, hodnota):
        #---- vnorena rekurzivna funkcia ----
        def nachadza_sa(vrch, hodnota):
            if vrch is None:
                return False
            return vrch.data==hodnota or nachadza_sa(vrch.left, hodnota) or nachadza_sa(vrch.right, hodnota)
        #----
        return nachadza_sa(self.root, hodnota)

Všimnite si ako sme zjednodušili poslednú z metód, ktorá zisťuje, či sa nejaká hodnota nachádza niekde v strome:

  • namiesto troch za sebou idúcich if-príkazov, sme zapísali jeden logický výraz, v ktorom sú podvýrazy spojené logickou operáciou or - toto označuje, že takýto výraz sa bude vyhodnocovať zľava doprava:
    • najprv vrch.data == hodnota: ak je to True, ďalšie podvýrazy sa nevyhodnocujú a celkový výsledok je True, inak sa spustí vyhodnocovanie nachadza_sa(vrch.left, hodnota)
    • nachadza_sa(vrch.left, hodnota) spustí rekurzívne zisťovanie, či sa daná hodnota nachádza v ľavom podstrome: ak áno celkový výsledok je True inak sa ešte spustí posledný podvýraz nachadza_sa(vrch.right, hodnota)
    • nachadza_sa(vrch.right, hodnota) spustí rekurzívne zisťovanie, či sa daná hodnota nachádza v pravom podstrome: ak áno celkový výsledok je True inak False

Pozrime sa ešte na parameter hodnota vo funkcii nachadza_sa():

  • do tohto parametra sme priradili hodnotu parametra metódy __contains__() s rovnakým menom
  • pričom, keby vnorená funkcia nachadza_sa() nemala hodnota ako svoj parameter, tak by videla na parameter hodnota nadradenej funkcie __contains__()
  • takže poučenie: keď vnorená funkcia chce používať nejakú premennú z nadradenej funkcie (kde je vnorená), nemusí ju dostať ako parameter, ale môže ju priamo používať (teda môže pracovať s jej hodnotou, ale meniť ju takto nevieme)

Zapíšme trochu vylepšenú verziu metódy __contains__():

class BinarnyStrom:

    ...

    def __contains__(self, hodnota):
        #---- vnorena rekurzivna funkcia ----
        def nachadza_sa(vrch):
            if vrch is None:
                return False
            return vrch.data == hodnota or nachadza_sa(vrch.left) or nachadza_sa(vrch.right)
        #----
        return nachadza_sa(self.root)

Metódu sme nazvali __contains__(), vďaka čomu ju môžeme volať nielen takto:

>>> strom.__contains__(123)
True

ale aj

>>> 123 in strom
True

29.1. Prechádzanie vrcholov stromu

Globálnu funkciu vypis(), ktorá v nejakom poradí vypisuje hodnoty vo všetkých vrcholoch:

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

prepíšme ako metódu stromu a otestujme:

class BinarnyStrom:
    ...

    def vypis(self):
        #---- vnorena rekurzivna funkcia ----
        def vypis_rek(vrch):
            if vrch is None:
                return
            print(vrch.data, end=' ')
            vypis_rek(vrch.left)
            vypis_rek(vrch.right)
        #----
        vypis_rek(self.root)
        print()

Vytvorili sme novú metódu vypis(), ktorá v svojom tele opäť obsahuje len tri príkazy: definíciu vnorenej (lokálnej) funkcie vypis_rek(), jej zavolanie s referenciou na koreň stromu a ukončenie vypisovaného riadka. Táto metóda (podobne ako skoro všetky doterajšie) obíde všetky vrcholy v strome tak, že najprv spracuje koreň stromu (vypíše ho príkazom print()), potom rekurzívne celý ľavý podstrom a na záver celý pravý podstrom.

Pozrime, akú postupnost dostávame z náhodného stromu:

binárny strom
>>> s = BinarnyStrom('abcdefghijkl')
>>> s.kresli()
>>> s.vypis()
a d i e k l f b g j h c

Naozaj sa najprv vypísal koreň stromu 'a' a pokračovalo sa vo vypisovaní celého ľavého podstromu. Tento ľavý podstrom má koreň 'd' (vypísalo sa druhé písmeno) a opäť sa rekurzívne pokračovalo v ľavom podstrome ľavého podstromu teda s koreňom 'i' (vypísalo sa tretie písmeno). Keďže tento podstrom už nemá žiadne ďalšie vrcholy, toto rekurzívne volanie končí a pokračuje sa s pravým podstromom stromu s koreňom 'd', teda so stromom s 'e' (štvrté písmeno). Takto sa rekurzívne prejde celý strom.

Mohli by sme si graficky znázorniť trasu po ktorej sme takto prešli:

obchádzanie vrcholov binárneho stromu

Obchádzame celý strom ale z vonkajšej strany pričom vždy, keď sa nachádzame naľavo od nejakého vrcholu, tak vypíšeme jeho hodnotu. Zakreslime si tieto prípady červenými šípkami:

obchádzanie vrcholov binárneho stromu so šípkami

Tomuto budeme hovoriť poradie spracovania preorder, keďže v rekurzívnej funkcii sa najprv spracuje hodnota vo vrchole a až potom sa spracovávajú ľavý a pravý podstrom. Vo všeobecnosti algoritmus preorder poradia zapíšeme:

class BinarnyStrom:
    ...

    def preorder(self):
        #---- vnorena rekurzivna funkcia ----
        def preorder_rek(vrch):
            if vrch is None:
                return
            # spracuj samotný vrchol vrch
            preorder_rek(vrch.left)
            preorder_rek(vrch.right)
        #----
        preorder_rek(self.root)

alebo to isté zapísané aj trochu inak:

class BinarnyStrom:
    ...

    def preorder(self):
        #---- vnorena rekurzivna funkcia ----
        def preorder_rek(vrch):
            # spracuj samotný vrchol vrch
            if vrch.left is not None:
                preorder_rek(vrch.left)
            if vrch.right is not None:
                preorder_rek(vrch.right)
        #----
        if self.root is not None:
            preorder_rek(self.root)

Závisí od riešeného problému, ktorú z týchto verzií použijete. Všimnite si, že aj metódy __len__(), vyska(), __contains__(), sucet() boli tvaru preorder.

Pre nás je zaujímavý výpis z tohto preorder poradia: tento výpis závisí od tvaru binárneho stromu a bude užitočné, keď to budete vedieť nasimulovať aj ručne.

Okrem poradia preorder poznáme ešte tieto základné poradia obchádzania vrcholov stromu:

  • inorder - najprv ľavý podstrom, potom samotný vrchol a na záver pravý podstrom
  • postorder - najprv ľavý podstrom, potom pravý podstrom a na záver samotný vrchol
  • po úrovniach - vrcholy sa spracovávajú v poradí ako sú vzdialené od koreňa, t.j. najprv koreň, potom obaja jeho synovia, potom všetci vnuci, atď.

Zapíšme prvé dve metódy:

class BinarnyStrom:
    ...

    def inorder_vypis(self):
        #---- vnorena rekurzivna funkcia ----
        def vypis_rek(vrch):
            if vrch is None:
                return
            vypis_rek(vrch.left)
            # spracuj samotný vrchol vrch
            print(vrch.data, end=' ')
            vypis_rek(vrch.right)
        #----
        vypis_rek(self.root)
        print()

    def postorder_vypis(self):
        #---- vnorena rekurzivna funkcia ----
        def vypis_rek(vrch):
            if vrch is None:
                return
            vypis_rek(vrch.left)
            vypis_rek(vrch.right)
            # spracuj samotný vrchol vrch
            print(vrch.data, end=' ')
        #----
        vypis_rek(self.root)
        print()

Ak otestujeme tieto výpisy pre náš náhodne generovaný strom, dostávame:

>>> s.inorder_vypis()
i d k l e f a j g h b c
>>> s.postorder_vypis()
i l k f e d j h g c b a

Všimnite si, že keď v predchádzajúcom obrázku s obchádzaním vrcholov a s červenými šípkami vľavo od vrcholov presunieme šípky pod každý vrchol, dostávame inorder poradie:

obchádzanie vrcholov binárneho stromu inorder

Podobne to bude, keď šípky presunieme vpravo od vrcholov dostaneme postorder poradie:

obchádzanie vrcholov binárneho stromu inorder

Tieto metódy by sa dali prepísať ako funkcie, ktoré vrátia znakový reťazec alebo pole, napr.

class BinarnyStrom:
    ...

    def preorder_str(self):
        #---- vnorena rekurzivna funkcia ----
        def retazec(vrch):
            if vrch is None:
                return ''
            return str(vrch.data) + ' ' + retazec(vrch.left) + retazec(vrch.right)
        #----
        return retazec(self.root)

    def preorder_list(self):
        #---- vnorena rekurzivna funkcia ----
        def urob_pole(vrch):
            if vrch is None:
                return []
            return [vrch.data] + urob_pole(vrch.left) + urob_pole(vrch.right)
        #----
        return urob_pole(self.root)

Tieto algoritmy postupného prechádzania všetkých vrcholov v nejakom poradí sa môžu využiť napr. na postupnú zmenu hodnôt vo vrcholoch stromu. Použijeme počítadlo, ktorého hodnotu budeme pri prechádzaní stromu priraďovať a za každým ho budeme zvyšovať o 1. Toto počítadlo ale nemôže byť obyčajná lokálna premenná, lebo ju chceme meniť počas behu rekurzie a chceme, aby sa táto zmenená hodnota zapamätala. Preto môžeme počítadlo vyrobiť ako atribút triedy, s ktorým už tento problém nebude.

Nasledovná metóda ilustruje spôsob očíslovania vrcholov v strome v poradí preorder, koreň bude mať hodnotu 1:

class BinarnyStrom:
    ...

    def ocisluj(self):
        #---- vnorena rekurzivna funkcia ----
        def ocisluj_rek(vrch):
            if vrch is None:
                return
            vrch.data = self.cislo
            self.cislo += 1
            ocisluj_rek(vrch.left)
            ocisluj_rek(vrch.right)
        #----
        self.cislo = 1
        ocisluj_rek(self.root)

Pri podobných úlohách veľmi často existuje niekoľko veľmi rozdielnych spôsobov riešení. Toto isté môžeme dosiahnuť aj inak, napr. tak, že počítadlom nebude atribút (stavová premenná inštancie) ale ďalší parameter rekurzívnej vnorenej funkcie. V tomto prípade, ale budeme od tejto pomocnej funkcie vyžadovať, aby nám oznámila, koľko čísel z počítadla v danom podstrome už minula. Inými slovami, funkcia bude vracať hodnotu počítadla, na ktorom skončila pri číslovaní vrcholov v podstrome:

class BinarnyStrom:
    ...

    def ocisluj(self):
        #---- vnorena rekurzivna funkcia ----
        def ocisluj_rek(vrch, cislo):
            if vrch is None:
                return cislo
            vrch.data = cislo
            cislo = ocisluj_rek(vrch.left, cislo+1)
            return ocisluj_rek(vrch.right, cislo)
        #----
        ocisluj_rek(self.root, 1)

Takže vnorená funkcia najprv očísluje vrchol, v ktorom sa nachádza (lebo je to preorder), potom očísluje vrcholy v ľavom podstrome a dozvie sa (ako výsledok funkcie) s akým číslom sa bude pokračovať v pravom podstrome. Na záver vráti novú hodnotu počítadla ako výsledok funkcie.

29.2. Prechádzanie po úrovniach

Tento algoritmus bude používať dátovú štruktúru queue (rad, front) takto:

  • na začiaku vyrobíme prázdny rad a vložíme do neho koreň stromu (čo je referencia na vrchol)
  • potom sa v cykle bude robiť nasledovné:
    • z radu sa vyberie prvý čakajúci vrchol (dequeue)
    • spracuje sa tento vrchol, napr. sa pomocou print() vypíše jeho hodnota
    • na koniec frontu sa vložia (enqueue) obaja synovia spracovávaného vrcholu
  • po skončení cyklu (práve boli spracované všetky vrcholy) sa môže urobiť nejaký záverečný úkon, napr. ukončiť rozpísaný riadok s výpisom vrcholov

Metóda, ktorá vypisuje hodnoty vo vrcholoch, ale prechádza strom po úrovniach, može vyzerať takto:

class BinarnyStrom:
    ...

    def vypis_po_urovniach(self):
        if self.root is None:
            return
        q = [self.root]                # q = Queue(); q.enqueue(self.root)
        vypis = 0
        while q != []:                 # while not q.is_empty():
            vrch = q.pop(0)            # vrch = q.dequeue()
            #spracuj
            print(vrch.data, end=' ')
            if vrch.left is not None:
                q.append(vrch.left)    # q.enqueue(vrch.left)
            if vrch.right is not None:
                q.append(vrch.right)   # q.enqueue(vrch.right)
        print()

V zápise funkcie môžete vidieť, aké operácie so štruktúrou rad sme nahradili operáciami s obyčajným poľom.

Po otestovaní, pre náš náhodný strom dostávame takéto poradie:

>>> s.vypis_po_urovniach()
a d b i e g c k f j h l

Ďalšia verzia pridáva do výpisu informáciu o konkrétnej úrovni - vrcholy, ktoré sú v rovnakej úrovni sa vypisujú do riadku a na nový riadok sa prejde vtedy, keď spracovávame vrchol z vyššej úrovne ako doteraz. Idea v tejto funkcii je taká, že do radu okrem samotného vrcholu z predchádzajúcej verzie budeme vkladať aj číslo úrovne. Preto, pri vyberaní vrcholu z radu, získavame aj jeho úroveň. Tiež musíme túto úroveň ukladať do radu, keď tam vkladáme nové vrcholy (synov momentálneho vrcholu):

class BinarnyStrom:
    ...

    def vypis_po_urovniach(self):
        if self.root is None:
            return
        q = [(self.root, 0)]
        vypis = 0
        while q != []:
            vrch, uroven = q.pop(0)
            #spracuj
            if vypis != uroven:
                print()
            print(vrch.data, end=' ')
            vypis = uroven
            if vrch.left is not None:
                q.append((vrch.left, uroven+1))
            if vrch.right is not None:
                q.append((vrch.right, uroven+1))
        print()

Obe tieto metódy sú nerekurzívne. Toto je veľmi dôležitá vlastnosť tohto algoritmu (hovorí sa mu aj algoritmus do šírky). Pomocou idey týchto algoritmov vieme riešiť veľkú skupinu úloh so stromami, napr.

  • zisťovanie, v ktorej úrovni sa nachádza ten ktorý vrchol
  • zisťovanie šírky stromu - čo je maximum z počtu vrcholov v jednotlivých úrovniach
  • zisťovanie všetkých vrcholov, ktoré sú v jednej úrovni
  • úlohy, ktoré sa dajú riešiť rekurzívne (napr. výška, počet vrcholov, apod.) ale ich nerekurzívne riešenie zabezpečí to, že takáto funkcia nespadne na pretečení rekurzie (čo je do 1000).

29.3. Cvičenie

  1. Zostavte triedu BinarnyStrom z prednášky aj so všetkými tam uvedenými metódami.

    • otestujte náhodné generovanie stromu so 16 vrcholmi s hodnotami 'x'
    • otestujte všetky typy výpisov pre strom s 10 vrcholmi s číslami 0 až 9
    • naprogramujte metódu count(hodnota) - metóda vráti počet vyskytov nejakej hodnoty, napr.
    >>> strom = BinarnyStrom('mama ma emu a ema ma mamu')
    >>> strom.count('m')
    8
    >>> 'mama ma emu a ema ma mamu'.count('m')
    8
    
  2. Pre daný strom

    binárny strom
    • ručne vypíšte postupnosti:

      1. preorder
      2. inorder
      3. postorder
      4. po úrovniach
  3. Pre daný strom

    binárny strom
    • ručne vpíšte hodnoty tak, aby vypisom pre postupnosť:

      1. preorder bolo 'programovanie'
      2. inorder bolo 'programovanie'
      3. postorder bolo 'programovanie'
      4. po úrovniach bolo 'programovanie'
  4. Nevieme, ako vyzerá nejaký binárny strom, ale poznáme jeho inorder a postorder.

    • dané poradia:
    inorder =  2 8 3 5 9 1 7 4 10 6
    postorder =  8 2 5 3 7 1 10 6 4 9
    
    • ručne zostavte preorder
  1. Ručne nakreslite všetky binárne stromy, ktoré majú 3 vrcholy a sú očíslované hodnotami 1, 2, 3 a to po úrovniach.

    • ku každému nakreslenému stromu vypíšte jeho inorder
  2. Do triedy BinarnyStrom dopíšte metódy:

    • mapuj(funkcia) - zmení hodnotu v každom vrchole aplikovaním danej funkcie
    class BinarnyStrom:
    
        ...
    
        def mapuj(self, funkcia):
            ...
            vrch.data = funkcia(vrch.data)
            ...
    
    >>> strom = BinarnyStrom(...)
    >>> strom.mapuj(lambda x: x*11)
    
    • inorder_ocisluj(start=0, krok=1) - očísluje všetky vrcholy celými číslami od hodnoty start s krokom krok tak, že inorder_výpis() vypíše usporiadanú postuposť čísel začínajúcu od zadaného štartu s daným krokom
    class BinarnyStrom:
    
        ...
    
        def inorder_ocisluj(self, start=0, krok=1):
            ...
    
    >>> strom = BinarnyStrom('Python')
    >>> strom.inorder_ocisluj(3, 5)
    >>> strom.inorder_vypis()
    3 8 13 18 23 28
    
    • prirad(pole) - postupne vyberá prvky poľa a priraďuje ich do vrcholov poľa v poradí preorder; ak je prvkov v poli menej ako vrcholov stromu, zvyšné vrcholy ostanú bezo zmeny
    class BinarnyStrom:
    
        ...
    
        def prirad(self, pole):
            ...
    
    >>> strom = BinarnyStrom('x'*10)
    >>> strom.prirad([2, 3, 5, 7, 11, 13])
    >>> strom.vypis()                       # preorder_vypis()
    2 3 5 7 11 13 x x x x
    
    • brat(vrchol) - funkcia vráti referenciu na brata zadaného vrcholu, resp. None, ak taký neexistuje
    class BinarnyStrom:
    
        ...
    
        def brat(self, vrchol):
            ...
    
    >>> strom = BinarnyStrom('python')
    >>> strom.kresli()
    >>> b = strom.brat(strom.root.right)
    >>> b.data
    ???
    
    • ity(i) - vráti hodnotu v i-tom vrchole (ak by sme ho prechádzali preorderom), nemali by ste konštruovať celú preorder postupnosť, ale treba zavolať preorder-algoritmus a ukončiť ho pri i-tom vrchole
    class BinarnyStrom:
    
        ...
    
        def ity(self, i):
            ...
    
    >>> strom = BinarnyStrom(range(10))
    >>> strom.prorder_vypis()
    ...
    >>> for i in range(len(strom)):
            print(strom.ity(i), end=' ')
    ...
    

    oba výpisy vypíšu rovnakú postupnosť

    • kopia() - vráti kópiu celého stromu, t.j. novú inštanciu triedy BinarnyStrom, v ktorej sa vyrobila kópia každého vrcholu pôvodného stromu
    class BinarnyStrom:
    
        ...
    
        def kopia(self):
            ...
    
    >>> strom = BinarnyStrom('programovanie')
    >>> kopia = strom.kopia()
    >>> strom.inorder_vypis()
    ...
    >>> kopia.inorder_vypis()
    ...
    

    oba výpisy vypíšu rovnakú postupnosť

  3. Využitím algoritmu prechádzania po úrovniach (vypis_po_urovniach()) naprogramujte tieto metódy:

    • ocisluj_po_urovniach(start=0, krok=1) - očísluje všetky vrcholy celými číslami od hodnoty start s krokom krok
    • v_urovni(k) - vráti pole (typu list) vrcholov (ich hodnôt) v danej úrovni, pre k=0 zoznam obsahuje jedinú hodnotu v koreni stromu
    • sirka() - zistí šírku stromu
    class BinarnyStrom:
    
        ...
    
        def ocisluj_po_urovniach(self, start=0, krok=1):
            ...
    
        def v_urovni(self, k):
            ...
    
        def sirka(self):
            ...
    
    >>> strom = BinarnyStrom(...)
    >>> strom.ocisluj_po_urovniach(1)
    >>> strom.kresli()
    >>> for k in range(strom.vyska()):
            print('v urovni', k, '=', strom.v_urovni(k))
    v urovni 0 = [...]
    v urovni 1 = [...]
    v urovni 2 = [...]
    ...
    >>> print('sirka =', strom.sirka())
    sirka = ...
    
  4. Nasledovné rekurzívne metódy prepíšte pomocou algoritmu po úrovniach na ich nerekurzívne verzie:

    • vyska()
    • __len__()
    • sucet()
    class BinarnyStrom:
    
        ...
    
        def vyska_nerek(self):
            ...
    
        def pocet_nerek(self):
            ...
    
        def sucet_nerek(self):
            ...
    
    >>> strom = BinarnyStrom(range(100))
    >>> print('vyska =', strom.vyska(), strom.vyska_nerek())
    vysk = ??? ???
    >>> print('pocet =', strom.pocet(), strom.pocet_nerek())
    pocet = 100 100
    >>> print('sucet =', strom.sucet(), strom.sucet_nerek())
    sucet = 4950 4950
    

29.4. Domáce zadanie

Napíšte modul s menom uloha6.py, ktorý bude obsahovať jedinú triedu s ďalšími dvomi vnorenými podtriedami a týmito metódami:

class FamilyTree:

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

    class Queue:
        def __init__(self):
            ...

        def is_empty(self):
            ...

        def enqueue(self, data):
            ...

        def dequeue(self):
            ...

    # ----------------------------

    def __init__(self, meno_suboru):
        self.root = ...
        ...

    def __len__(self):
        ...

    def depth(self, data):
        ...

    def height(self):
        ...

    def width(self):
        ...

    def subtree_num(self, data):
        ...

    def descendant(self, data1, data2):
        ...

    def level_set(self, k):
        ...

    def leaves_num(self):
        ...

Trieda bude riešiť takúto úlohu:

  • budeme zostavovať rodokmeň panovníckej rodiny vymysleného kráľovstva
  • keďže každý člen tejto rodiny mal maximálne dvoch potomkov, na reprezentáciu rodokmeňa použijeme binárny strom
  • informácie o rodinných vzťahoch sú uložené v textovom súbore: v každom riadku je dvojica mien rodič-potomok (oddelené sú znakom ‚-‚), súbor môže vyzerať napr. takto:
Predslav-Vladimir
Miroslav-Boleslav
Predslav-Kazimir
Braslav-Rastislav
Drahomir-Lubomir
Ludovit-Mojmir
Svatopluk-Miroslav
Stanislav-Predslav
Jaroslav-Stanislav
Kazimir-Pravoslav
Svatopluk-Jaroslav
Vlastimil-Bohuslav
Jaroslav-Ludovit
Bohumir-Ladislav
Vlastimil-Svetomir
Bohumir-Vlastimil
Miroslav-Bohumir
Boleslav-Drahomir
Boleslav-Braslav
  • tento súbor (je to prvý testovací súbor 'subor1.txt') reprezentuje takýto rodokmeň (uvedomte si, že v samotnom súbore nie je informácia o tom, ktorý z potomkov je ľavý a ktorý pravý, preto správny rodokmeň je ľubovoľný strom, ktorý zodpovedá týmto dvojiciam zo súboru):
binárny strom
  • všimnite si, že riadkov v súbore je presne o jeden menej, ako je vrcholov v strome - totiž každý vrchol okrem koreňa je niekoho potomkom a teda sa nachádza práve v jednom riadku súboru ako potomok (na druhom mieste dvojice)
  • koreňom stromu je zrejme ten jediný vrchol, ktorý medzi potomkami chýba

Metódy triedy FamilyTree by mali mať túto funkčnosť (môžete si dodefinovať aj ďalšie pomocné metódy):

__init__(meno_suboru)

  • prečíta zadaný textový súbor a vytvorí z neho binárny strom s koreňom v self.root (všetky vrcholy musia byť typu self.Node)
  • môžete predpokladať, že súbor je zadaný korektne:
    • každý riadok obsahuje dvojicu mien oddelených znakom '-'
    • prvé meno v dvojici je niektorý rodič, druhé meno je jeho potomok
    • keďže tieto dvojice sú v súbore v náhodnom poradí, musíte vymyslieť nejakú ideu, ako celý strom skonštruujete (môžete využiť napr. typy dict a set)

__len__()

  • vráti počet vrcholov v strome

subtree_num(data)

  • nájde vrchol so zadaným údajom a vráti počet vrcholov v podstrome, ktorý začína od tohto vrcholu
    • ak sa zavolá s údajom v koreni stromu, tak vráti počet všetkých vrcholov v strome (to isté ako len(strom))
    • ak sa zavolá s údajom v liste stromu, tak vráti 1 (podstrom má len tento jeden vrchol)
    • ak sa v strome zadaný údaj nenachádza, funkcia vráti 0

height()

  • vráti výšku stromu

depth(data)

  • vráti hĺbku vrcholu
  • ak vrchol so zadaným data neexistuje, metóda vráti None

width()

  • vráti šírku stromu

descendant(data1, data2)

  • zistí, či data2 je jeden z potomkov pre vrchol data1
  • metóda vráti True, ak áno, inak vráti False

level_set(k)

  • vráti množinu všetkých údajov na zadanej úrovni:
    • pre k==0 vráti jednoprvkovú množinu s koreňom stromu
    • pre k==1 vráti dvojprvkovú množinu potomkov koreňa
    • ak je k väčšie ako počet úrovní stromu (výška), funkcia vráti prázdnu množinu

leaves_num()

  • funkcia vráti počet všetkých listov stromu

Keď budete testovať vaše riešenie, môžete na koniec modulu pridať napr. takýto kód:

if __name__ == '__main__':
    f = FamilyTree('subor1.txt')
    print('pocet vrcholov =', len(f))
    print('podstrom pre Bohumir =', f.subtree_num('Bohumir'))
    print('podstrom pre Robert =', f.subtree_num('Robert'))
    print('vyska =', f.height())
    print('sirka =', f.width())
    print('hlbka vrcholu Vlastimil =', f.depth('Vlastimil'))
    print('Miroslav ma potomka Bohuslav =', f.descendant('Miroslav','Bohuslav'))
    print('Jaroslav ma potomka Svatopluk =', f.descendant('Jaroslav','Svatopluk'))
    print('vrcholy na urovni 2 =', f.level_set(2))
    print('vrcholy na urovni 10 =', f.level_set(10))
    print('pocet listov =', f.leaves_num())

Tento konkrétny test by mal vypísať:

pocet vrcholov = 20
podstrom pre Bohumir = 5
podstrom pre Robert = 0
vyska = 5
sirka = 6
hlbka vrcholu Vlastimil = 3
Miroslav ma potomka Bohuslav = True
Jaroslav ma potomka Svatopluk = False
vrcholy na urovni 2 = {'Boleslav', 'Bohumir', 'Ludovit', 'Stanislav'}
vrcholy na urovni 10 = set()
pocet listov = 8

Váš program sa bude testovať so 4 rôznymi súbormi:

  1. súbor má 20 vrcholov
  2. súbor má 63 vrcholov
  3. súbor má skoro 1000 vrcholov
  4. súbor má skoro 100000 vrcholov

Binárny strom pre 4. testový súbor je tak veľký, že na ňom nepobeží rekurzia. Preto bude treba všetky metódy prepísať bez použitia rekurzie (môžete použiť ideu nerekurzívnej metódy vypis_po_urovnach()).

V moduloch nič nevypisujte a tiež nevolajte žiadne ďalšie príkazy mimo definícií triedy.

Váš odovzdaný modul s menom uloha6.py by mal začínať dvomi riadkami komentárov (s vašim menom):

# autor: Janko Hrasko
# uloha: 6. domace zadanie Rodokmen