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.

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

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

def vypis(vrch, k=0):        # funkcia z predchádzajúcich cvičení
   if vrch is None:
       return
   print('.'*k, vrch.data)
   vypis(vrch.left, k+2)
   vypis(vrch.right, k+2)

strom = Vrchol(1, Vrchol(2, None, Vrchol(3)), Vrchol(4))
vypis(strom)
print('sucet =', sucet(strom))

Dostávame takýto výpis:

 1
.. 2
.... 3
.. 4
sucet = 10

Prirodzenejšie a programátorsky správnejšie by bolo zadefinovanie triedy Binárny 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:

    #------ vnorená trieda ------

    class Vrchol:
        def __init__(self, data, left=None, right=None):     # inicializácia triedy Vrchol
            self.data, self.left, self.right = data, left, right

    #------ koniec definície vnorenej triedy ------

    def __init__(self):      # inicializácia triedy BinarnyStrom
        self.root = None

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

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

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:

import random

class BinarnyStrom:

    #------ vnorená trieda ------

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

    #------ koniec definície vnorenej triedy ------

    def __init__(self, postupnost=None):
        self.root = None
        if postupnost is not None:
            for hodnota in postupnost:
                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 random.randrange(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))

Teraz prerobíme jednu jednoduchšiu rekurzívnu funkciu sucet() na metódu. Najprv len zavolaním tejto globálnej funkcie:

class BinarnyStrom:

    #------ vnorená trieda ------

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

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

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

    ...

    def sucet(self):
        return sucet_rek(self.root)

# --- globálna funkcia ---
def sucet_rek(vrch):
    if vrch is None:
        return 0
    return vrch.data + sucet_rek(vrch.left) + sucet_rek(vrch.right)

Aby bola čitateľnejšia metóda sucet(), pôvodnú rekurzívnu funkciu sme premenovali na sucet_rek(). Takáto verzia funguje, ale programátorsky správnejšie bude, keď sucet_rek() nebude globálna, ale súčasťou triedy BinarnyStrom, napr. bude vnorená v metóde sucet():

class BinarnyStrom:

    ...

    def sucet(self):
        # --- vnorená rekurzívna funkcia ---
        def sucet_rek(vrch):
            if vrch is None:
                return 0
            return vrch.data + sucet_rek(vrch.left) + sucet_rek(vrch.right)
        # --- koniec vnorenej funkcie ---
        return sucet_rek(self.root)

Teraz sa môžeme pustiť do rekurzívnej funkcie kresli(), ktorá vykresľuje strom do grafickej plochy:

import tkinter

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

canvas = tkinter.Canvas(width=600, height=300, bg='white')
canvas.pack()

strom = BinarnyStrom('abcdefghijkl')
kresli(strom.root, 300, 300, 30)

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

  1. canvas je globálna premenná, hoci nám by sa asi viac hodil triedny atribút, ktorý by bol spoločný pre všetky inštancie

  2. canvas by bolo vhodné inicializovať až pri prvom zavolaní metódy kresli() (nesmieme to inicializovať ako self.canvas=tkinter.Canvas(...), lebo takto by sa triedny atribút prekryl inštančným atribútom)

  3. strom sa bude automaticky kresliť odhora 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ť:

import random
import tkinter

class BinarnyStrom:

    canvas = None            # triedny atribút

    #------ vnorená trieda ------

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

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

    ...

    def kresli(self):

        #---- vnorená rekurzívna funkcia ----

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

        #----

        if self.canvas is None:
            BinarnyStrom.canvas = tkinter.Canvas(width=600, height=300, bg='white')
            self.canvas.pack()
        self.canvas.delete('all')
        kresli_rek(self.root, 300, 300, 30)

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

  3. pri prvom zavolaní metódy kresli() má atribút canvas zatiaľ hodnotu None, preto treba vytvoriť grafickú plochu pomocou BinarnyStrom.canvas = tkinter.Canvas(...)

  4. pred každým vykresľovaním stromu 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 štruktúry __len__(), zapísať inak. Opäť to urobíme podobne ako s metódami sucet() a kresli():

class BinarnyStrom:

    ...

    def __len__(self):
        #---- vnorená rekurzívna 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ť. Prepíšme niektoré ďalšie rekurzívne funkcie ako metódy triedy BinarnyStrom:

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

Teraz ako metódy:

class BinarnyStrom:

    ...

    def vyska(self):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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

Prechádzanie vrcholov stromu

Globálnu funkciu vypis(), ktorá v nejakom poradí vypisuje hodnoty vo všetkých vrcholoch, sme teraz upravili tak, aby sa všetky hodnoty vypisovali do jedného riadku:

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

Prepíšme ju ako metódu stromue:

class BinarnyStrom:
    ...

    def vypis(self):
        #---- vnorená rekurzívna 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ú postupnosť 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):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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 zoznam, napr.

class BinarnyStrom:
    ...

    def preorder_str(self):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna funkcia ----
        def urob_zoznam(vrch):
            if vrch is None:
                return []
            return [vrch.data] + urob_zoznam(vrch.left) + urob_zoznam(vrch.right)
        #----
        return urob_zoznam(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):
        #---- vnorená rekurzívna 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):
        #---- vnorená rekurzívna 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.

Prechádzanie po úrovniach

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

  • na začiatku 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, môž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)
        while q != []:                 # while not q.is_empty():
            vrch = q.pop(0)            # vrch = q.dequeue()
            # spracuj vrchol
            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 zoznamom.

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

Toto isté vieme dosiahnuť aj takýmto algoritmom (poštudujte a porovnajte):

class BinarnyStrom:
    ...

    def vypis_po_urovniach(self):
        if self.root is None:
            return
        uroven = [self.root]
        while uroven:
            dalsia_uroven = []
            for vrch in uroven:
                # spracuj vrchol
                print(vrch.data, end=' ')
                if vrch.left is not None:
                    dalsia_uroven.append(vrch.left)
                if vrch.right is not None:
                    dalsia_uroven.append(vrch.right)
            print()
            uroven = dalsia_uroven

Všetky tieto tri metódy sú nerekurzívne - závisí od vás, ktorú verziu kedy použijete. To. že sú nerekurzívne, 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).



Cvičenia

L.I.S.T.

  1. Zostav triedu BinarnyStrom z prednášky s metódami: pridaj_vrchol(), sucet(), kresli(), __len__(), vyska() a __contains__().

    • otestuj náhodné generovanie stromu so 16 vrcholmi, tak že vo všetkých vrcholch budú hodnoty 'x'

    • prekontroluj na takomto strome funkčnosť metód __len__(), vyska() a __contains__()

    • vygeneruj náhodný strom s náhodnými číslami vo vrcholoch: napr. 10 vrcholov s náhodnými číslami od 0 do 5

    • na takomto strome over funkčnosť metódy sucet()


  1. Do triedy BinarnyStrom pridaj metódu count(hodnota), ktorá rekurzívne prejde všetky vrcholy stromu a vráti počet výskytov zadanej 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
      

  1. Do triedy BinarnyStrom pridaj metódy z prednášky: preorder_vypis(), inorder_vypis(), postorder_vypis() a vypis_po_urovniach()

    • otestuj všetky tieto typy výpisov pre náhodný strom s 10 vrcholmi s číslami 1 až 10


  1. Pre daný strom

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

      1. preorder

      2. inorder

      3. postorder

      4. po úrovniach

    • potom zostav a nakresli presne takýto istý strom a spusti vypisovacie metódy, aby si skontroloval svoje ručne vytvorené výpisy, napr.

      >>> strom = BinarnyStrom()
      >>> ...
      >>> strom.kresli()
      >>> strom.preorder_vypis()
      ...
      

  1. Do daného stromu

    binárny strom
    • ručne vpíš hodnoty tak, aby výpisom pre postupnosť:

      1. preorder bolo 'programovanie'

      2. inorder bolo 'programovanie'

      3. postorder bolo 'programovanie'

      4. po úrovniach bolo 'programovanie'

    • zrejme takto dostaneš štyri rôzne vyplnené stromy, ktoré všetky majú rovnaký tvar; aspoň jeden z nich zostav podobne ako v úlohe (4) a skontroluj príslušný výpis


  1. Nevieme, ako vyzerá nejaký binárny strom (jeho tvar), 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 zostav preorder

      • uvedom si, aký vrchol bude v koreni stromu (posledný v postorder)

      • vidíš, kde sa v inorder nachádza číslo v koreni - potom všetky vrcholy vľavo tvoria ľavý podstrom a všetky vpravo pravý podstrom

      • pre každý z týchto podstromov vieš (z výpisu postorder) aký majú koreň - to sú synovia koreňa

      • takto pokračuješ, kým nezostavíš celý strom

      • keď máš strom hotový, zisti jeho preorder

    • podobne, ako v úlohách (4) a (5) zostav a nakresli strom, ktorý si takto zostavil a spusti všetky štyri vypisovacie metódy pre kontrolu


  1. Ručne nakresli všetky binárne stromy, ktoré majú 3 vrcholy a sú očíslované hodnotami 1, 2, 3 a to po úrovniach.

    • potom ku každému nakreslenému stromu vypíš jeho inorder


  1. Do triedy BinarnyStrom dopíš 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ú postupnosť čísel začínajúcu od zadaného štartu s daným krokom (na prednáške sa robila podobná metóda, ktorá robila nejaké očíslovanie vo verzii preorder):

      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(postupnost) - postupne vyberá prvky z danej postupnosti (napr. list, tuple, str, …) a priraďuje ich do vrcholov stromu v poradí preorder; ak je prvkov v postupnosti menej ako vrcholov stromu, zvyšné vrcholy ostanú bezo zmeny

      class BinarnyStrom:
      
          ...
      
          def prirad(self, postupnost):
              ...
      
      >>> 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), nemala by sa pritom 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.preorder_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ť hodnôt


  1. Využitím algoritmu prechádzania po úrovniach (vypis_po_urovniach()) naprogramuj 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 zoznam (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 = ...
      

  1. Nasledovné rekurzívne metódy prepíš 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):
              ...
      
    • skontroluj ich s pôvodnými rekurzívnymi verziami:

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


6. Domáce zadanie

L.I.S.T.

Napíšte modul s menom riesenie6.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

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

    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:

  • budete 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ý syn a ktorý pravý syn, preto správny rodokmeň je ľubovoľný strom, ktorý zodpovedá týmto dvojiciam zo súboru):

    binárny strom s rodokmeňom
  • 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), v triede nepoužívajte štruktúrované atribúty (atribúty typu list, set, dict)

  • 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 s danou hodnotou (ako ďaleko je to od koreňa stromu k tomuto 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()).

Vaše riešenie odovzdajte v súbore riesenie6.py najneskôr do 14. apríla. Prvé tri riadky tohto súboru budú obsahovať (s vašim menom):

# 6. zadanie: rodokmen
# autor: Janko Hrasko
# datum: 31.3.2019