# v_0.10
# https://www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder

# BT (Node) Naive implementation

# 1. Naimplementujte třídou (class) Node pro vrcholy
# datové struktury BT (zatim bez operaci, a bez BST)

# Připomenutí BT
# BT: a) Node
#     b) None (Nic, Nill, ...)

# Node:
# ----------------
# |   Dato\Key   |
# ----------------
# | left | right |
# ----------------
# kde left a right jsou zase BT






class Node:
    def __init__(self, k, l=None, p=None):
        self.dato = k
        self.l = l
        self.p = p


# class Node:
#     def __init__(self, k):
#         self.dato = k
#         self.l = None
#         self.p = None


# 1.1 Rucne vytvorte zadaný BST (BT) t
# (zatim nemame zadne operace typu insert, delete, apod;
# strom tvorime "rucne" vhodným voláním)

# BST t
#         10
#    5          15
# 1     7    12    20


# vytvorim instanci Nodu s hodnotou 10
# a ulozim si ji do promenne t
t = Node(10)

# co mi vypise print(t)?
print(t)


print(t.dato)
print(t.l)
print(t.p)


# o(tazka): jak budeme postupovat nyni?

# pridam (rucne) vrcholy 5 a 15
t.l = Node(5)
t.p = Node(15)


# o: jak vypisu obsah vrcholu 5 a 10?


print(t.dato)
print(t.l)  # nyni uz vypisi adresu vrcholu 5
print(t.l.dato)
print(t.p.dato)

# z(adani): rucne dovytvorte zadany BST t


t.l.l = Node(1)
t.l.p = Node(7)
print(t.l.p.dato)

t.l.p.l = Node(6)
t.l.p.p = Node(8)

t.p.p = Node(30)
t.p.p.l = Node(25)

print(t.p.p.dato)

# zkuste vytvorit strom "na jeden radek" kodu
# ve smyslu rekurzvního vkladání vrcholů

# BST
#         10
#    5         20
# 1     7          30


t = Node(10, Node(5, Node(1), Node(7)), Node(20, None, Node(30)))
t = Node(10, Node(5, Node(1), Node(7)), Node(20, p=Node(30)))


# 2. Napiste rekurzivni funkci traverz(t),
# ktera systematicky (DFS) projde binarni strom
# a pro kazdy vrchol (prave jednou) vypise na konzoly hodnotu
# ve vrcholu ulozenou
# t je kořen stromu


# logika průchodu BT,
# kde garantovaně projdu všechny vrcholy danym systemem/podle pravidla
# a "nedělám zbytečnou práci"


# zkusme nejdrive navrhnout meta algoritmus


# idea:
#     a] proved akci/proces na vrholu t
#     b] rekuzivne spracuj potomky


def traverz(t):
    if t != None:
        print(t.dato)
        traverz(t.l)
        traverz(t.p)


# komentovana verze funkce traverz(t)
def traverz(t):
    # Co dostane funkce traverz za vstup?
    # BT ... Co je BT (dle def)?
    # Bud:  a) Node nebo za
    #       b) None

    if t != None:
        # kdyz None nedelam nic, koncim
        # kdyz Node vyresim ho
        print(t.dato)  # na vrcholu provedu akci

        # a vyresim potomky
        traverz(t.l)  # vyresim leveho potomka
        traverz(t.p)  # vyresim praveho potomka


# jeste nez si kod pustime, zkuste urcit jakou posloupnost hodnot
# tento rekurzuvni algorimus vypise; teoreticke cviceni


# a podivejme se na vysledek
traverz(t)

# poznamka: provedli jsme traverz bin stromem DFS preOrder


# 3. Mohu nejak zmenit poradi vypisu vrcholu? (stale rekurzivni dfs)


# note: prohodit volani z LP na PL


def traverzPL(t):
    if t != None:
        print(t.dato)
        traverzPL(t.p)
        traverzPL(t.l)


# jeste nez si kod pustime, zkuste urcit jakou posloupnost hodnot
# tento rekurzuvni algorimus vypise; teoreticke cviceni

traverzPL(t)

# Note: to by slo, ale neni to nyní az tak zajimave (do budoucna, volba vetve behu byva zasadni pro efektivitu algoritmu),
# snad jen dostali jsme vypis v poradi zasobniku
# a ano volba poradi spracovani podstromu je dulezity optimalizcni prvek,
# v tuto chvíli je beyond


# 4. tak zkusme to jinak? jiny napad? jak zmenit poradi vypisu?


def traverzPostOrder(t):
    if t != None:
        # print(t.dato)
        traverzPostOrder(t.l)
        # print(t.dato)
        traverzPostOrder(t.p)
        print(t.dato)


# a zase zkusme si nejdriv urcit poradi vypisu pred spustenim kodu
traverzPostOrder(t)

# poznamka: provedli jsme traverz DFS postOrder

# kdy provadime akci?
# kdyz vstupujeme do vrcholu vs kdyz vrchol ukoncujeme/opoustime
# resp.
# akce pred spracovanim potomku vs po jejich spracovani
# akce to tom kdyz uz znam vstupy/hodnoty/vysledky z potomku

# vycisleni aritmetickeho vyrazu ve reprezentaci stromu
# "vycisleni behu programu"


# 1.9 Projdete BST t tak, ze vypiste setridene hodnoty uzlu
# od nejmensiho k nejvetsimu


# pro bin stromy mame jeste INorder


def traverzInOrder(t):
    if t != None:
        # print(t.dato)
        traverzInOrder(t.l)
        print(t.dato)
        traverzInOrder(t.p)
        # print(t.dato)


traverzInOrder(t)

# https://www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder


# 4. Upravte funkci traverz(t) tak,
# aby spocitala soucet vsech cisel ve strome a vratila ho


def traverzSum(t):
    if t != None:
        return traverzSum(t.l) + traverzSum(t.p) + t.dato
    else:
        return 0


print(traverzSum(t))

# poznamka: (konecna) rekurze v principu obsahuje dve casti:
# a] rekurzivni volani
# b] zastavovaci podminku


# 4. Upravte funkci traverz tak,
# aby spocitala (maximalni) hloubku stromu a vratila ji
# hloubka stromu je definovana jako: delka nejdelsi cesty
# z korene stromu do nejakeho listu (mereno poctem hran cesty)

# co vlastne delame?
# a] prochazime strom a pocitame jeho nejakou globalni charakteristiku
# b] (zasadni) rozmyslime, jak funguje rekuzre resp pruchod stromem - coz potrebujeme k vypoctu charakteristiky
# c] (zasadni) jak predavat data behem rekurzivniho volani (mutable vs imutable)

# note: dva druhy rekurze: a] botom up rekurze, b] top down rekurze
# note: funkce vraci spatny vysledek. v cem je spatne a proc?


# nekorektni verze, proc vraci +1 vetsi hloubku?
# note: botom up rekurze
def traverzDepth(t):
    if t != None:
        return max(traverzDepth(t.l), traverzDepth(t.p)) + 1
    else:
        # musi zde byt 0? co vraci funkce, ktera neobsahuje return?
        return 0


print(traverzDepth(t))


# nekorektni verze, proc vraci +1 vetsi hloubku?
# note: top down rekurze
def traverzDepth(t, h=0):
    if t != None:
        return max(traverzDepth(t.l, h + 1), traverzDepth(t.p, h + 1))
    else:
        return h


print(traverzDepth(t))


# 5. Vytvorte funkci traverzReturnValues(t), ktera funguje analogicky jako funkce traverz,
# projde systematicky strom
# avsak hodnoty nevypisuje, ale vsechny je vraci ulozene v listu (binaryTree2List),
# kazdou prave jednou
# "projit strom a v listu vratit vsechny hodnoty"

# a] (prasarna) pres global variable
# b] lokal mutable var


# b]
def traverzReturnValues(t, l=[]):
    if t != None:
        l.append(t.dato)
        traverzReturnValues(t.l, l)
        traverzReturnValues(t.p, l)

    return l


print(traverzReturnValues(t))


# a]
l = []


def traverzReturnValuesGlob(t):
    if t != None:
        l.append(t.dato)
        traverzReturnValuesGlob(t.l)
        traverzReturnValuesGlob(t.p)

    return l


print("Glob variable: ", traverzReturnValuesGlob(t))
# print("Glob variable: ", l)


# 5.1 Rekurzivne projdete BT a spocitejte pocet vrcholu pro kazdou vrstve stromu
# Pro "nas" strom je to ve formatu:   
# vrstva: pocet nodu 
# 0:1
# 1:2
# 2:3
# popr [1,2,3]

# a] pomoci dict
# b] pomoci listu


def countNodesInTreeLayer(t, h=0, l=[]):
    if t != None:

        if len(l) <= h: # v hloubce jsem jeste nebyl, list je treba prodouzit
            l.append(0) # prodlouzeni listu
            l[h] += 1   # inkremetace za prave navstiveny vrchol
        else:   # v hloubce jsem jiz byl a prictu aktualni vrchol
            l[h] += 1

        countNodesInTreeLayer(t.l, h + 1, l)
        countNodesInTreeLayer(t.p, h + 1, l)

    return l


# print(len([]))
# countNodesInTreeLayer(None)
print(countNodesInTreeLayer(t))

# 5.2 Rekurzivne projdete BT a vratte list Listu,
# kde kazdy List obsahuje vrcholy dane vrstvy z leva doprava
#


def getListsNodesInTreeLayer(t, h=0, l=[]):
    if t != None:

        if len(l) <= h:
            l.append([t.dato])
        else:
            l[h].append(t.dato)

        getListsNodesInTreeLayer(t.l, h + 1, l)
        getListsNodesInTreeLayer(t.p, h + 1, l)

    return l


print(getListsNodesInTreeLayer(t))


# 6. Napiste funkci, ktera vytisknete vertikalne BT (kdy nahore je nejvetsi hodnota)
# velikost odsazeni je parametr (n cele kladne cislo) funkce,
# ktery udava pocet mezer za jednu vrstvu hloubky
# stale rekurzivni algoritmus
# (za "prazdne nody" se neprovadi tisk; co vrchol to jeden radek)

# Priklad

# pro zadany strom
#         10
#    5          15
# 1     7    12    20

# vytiskne
#         20
#     15
#         12
# 10
#         7
#     5
#         1


def printBTVert(t, n=3, h=0):
    if t != None:
        printBTVert(t.p, n, h + 1)
        # print(t.dato)
        # print(" "*(n*h), t.dato)
        print(f"{t.dato:{n*h}d}")
        printBTVert(t.l, n, h + 1)


printBTVert(t, 4)
printBTVert(t, 7)


# 7. Strom tisk horiz - treba fronta


# 9. Napište rekurzuvní funkci isPalindrom(string), která na vstupu dostane řetězec
# a vrátí True v případě, že se jedná o palindrom
# a False pokud se o palindrom nejedná; prázdný řetězec je považován na palindrom


def isPalindrom(str):
    print(str)

    if (len(str) == 0) or (len(str) == 1):
        return True
    else:
        if str[0] == str[-1]:
            # print(str[0]+" "+str[-1])
            return isPalindrom(str[1:-1])

        else:
            return False


print(isPalindrom("rotor"))
print(isPalindrom("r"))
print(isPalindrom("rr"))
print(isPalindrom("ro"))
print(isPalindrom("rrrr"))
print(isPalindrom("rrrro"))
print(isPalindrom(""))

# kviiiiz: co vypise? a proc?
print([].append(0))

s = []
s = s.append(0)
print(s)


# 10. Napište rekurzivní funkci reverse(list), která na vstupu dostane list
# a vrátí ho v obráceném (reverzním) pořadí


def reverse(list):
    if len(list) <= 1:
        return list
    else:
        head = list.pop(0)
        tail = list
        print(head)
        print(tail)

        reverse(tail).append(head)
        return tail


print(reverse([1, 2, 3]))
print(reverse([1, 2, 3, 4]))
print(reverse([1, 2, 3, 4, 5]))


# DALSI PRIKLDY SEM UZ NEPATRI

# 8.1 nalézt všechny různé rozklady daného čísla N na součet kladných celých sčítanců


# note: kod generuje stejne n-tice resp jejich permutace napr. [4, 1] = 5 a[1, 4] = 5
# reseni: generovat rostouci posloupnosti; neni implementovano
def rozklad(n, zbyvaRozlozit, l=[]):

    if sum(l) == n:
        print(l)
    else:
        if sum(l) > n:
            pass
        else:
            for i in range(zbyvaRozlozit):
                l.append(i + 1)
                rozklad(n, zbyvaRozlozit - i, l)
                l.pop()


rozklad(5, 5)