ALX - Kurs Python - Super Team

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

[20.02.2022] Zadania Drzewa

# zad 1 zbudowanie drzewa
# zad 2 zwrocenie slowa najdluzszego

#ZAD1
 
korzen = input('Podaj korzen')
drzewo_binarne = list()
 
drzewo_binarne.append(korzen)
 
while True:
    linia = input('podaj linie')
 
    if linia == 'end':
        break
 
    dane = linia.split()
    element = dane[1]
    sciezka = list(dane[0])
 
    idx = 0
 
    for e in sciezka:
        if e == 'L':
            idx = 2*idx + 1
        else:
            idx = 2*idx + 2
 
        while idx >= len(drzewo_binarne):
            drzewo_binarne.append(None)
 
        drzewo_binarne[idx] = '?'
 
    drzewo_binarne[idx] = element
 
    print(drzewo_binarne)

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

Odp: [20.02.2022] Zadania Drzewa

Zadanie 2 - moje rozwiązanie:

unikalna = []
posortowana = sorted(unikalna, key=len)

for e in drzewo_binarne:
    if e not in unikalna:
        unikalna.append(e)
        print(unikalna)
        print(posortowana)
        print(unikalna[-1])

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

Odp: [20.02.2022] Zadania Drzewa

Rozwiązanie rekurencyjne prowadzącego:

def najdluzsze_slowo(drzewo, idx):
    l = 0
    p = 0
    if idx*2+1 < len(drzewo):
        l = str(najdluzsze_slowo(drzewo,idx*2+1)) + str(drzewo[idx])
    if idx*2+2 < len(drzewo):
        p = str(najdluzsze_slowo(drzewo, idx *2+ 2)) + str(drzewo[idx])
    if l == 0 and p == 0:
        return str(drzewo[idx])
 
    if len(str(l)) < len(str(p)):
        return str(l)
    return str(p)
 
print(najdluzsze_slowo(drzewo_binarne, 0))