ALX - Kurs Python - Super Team

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

Drzewo

# 1 przechodzicie zawsze od 0 pozycji
# 2 wyzanczacie realcje
# I pozycja nie istnieje  -> dopisujemy tak duzo 0 az pozycja istneije, wstawiamy element
# II pozycja istnieje, element pusty -> wstawiamy element
# III pozycja istnieje, ale jest zajeta, sprawdzamy relacje jesli mniejsza lub rowna to szukamy 2 n +1
# IV pozycja istnieje, ale jest zajeta, sprawdzamy relacje jesli wieksza to szukamy 2 n +2

drzewo_binarne = list()

while True:
    element = int(input('Podaj element:'))
    czyWstawiony = False
    n = 0
    while not czyWstawiony:
        while n >= len(drzewo_binarne):
            drzewo_binarne.append(0)
        if drzewo_binarne[n] == 0:
            drzewo_binarne[n] = element
            czyWstawiony = True
        elif drzewo_binarne[n] >= element:
            n = 2*n+1
        else:
            n = 2*n+2

    print(drzewo_binarne)

Wiadomość dodana po 02 min 38 s:

Wiadomość dodana po 16 h 49 min 24 s:

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

Odp: Drzewo

BFS I DFS Pre Order

drzewo_binarne = list()
 
dane = [7,2,11,1,5,8,-3,2,4,7,11,-4,-2,4,5,10,7]
val = 0
while val < len(dane):
    # val = input('Podaj element:')
    # if val == 'end':
    #     break
    element = dane[val]
    val += 1
    czyWstawiony = False
    n = 0
    while not czyWstawiony:
        while n >= len(drzewo_binarne):
            drzewo_binarne.append(0)
        if drzewo_binarne[n] == 0:
            drzewo_binarne[n] = element
            czyWstawiony = True
        elif drzewo_binarne[n] >= element:
            n = 2*n+1
        else:
            n = 2*n+2
 
    print(drzewo_binarne)
 
 
 
def bfs(drzewo):
    print('BFS: ', end='')
    for node in drzewo:
        if node != 0:
            print(node, end=',')
bfs(drzewo_binarne)
 
print()
print('DFS Pre-order: ', end='')
def dfs_pre(drzewo, korzen):
    if drzewo[korzen] != 0:
        print(drzewo[korzen], end=', ')
    if(korzen*2+1 < len(drzewo)):
        dfs_pre(drzewo, korzen*2+1)
    if(korzen*2+2 < len(drzewo)):
        dfs_pre(drzewo, korzen*2+2)
 
dfs_pre(drzewo_binarne, 0)

Wiadomość dodana po 18 min 50 s:
IN Order i POST Order:

print()
print('DFS In-order: ', end='')
def dfs_in(drzewo, korzen):
    if (korzen * 2 + 1 < len(drzewo)):
        dfs_in(drzewo, korzen * 2 + 1)
    if drzewo[korzen] != 0:
        print(drzewo[korzen], end=', ')
    if(korzen*2+2 < len(drzewo)):
        dfs_in(drzewo, korzen*2+2)
 
dfs_in(drzewo_binarne, 0)
 
 
print()
print('DFS Post-order: ', end='')
def dfs_post(drzewo, korzen):
    if (korzen * 2 + 1 < len(drzewo)):
        dfs_post(drzewo, korzen * 2 + 1)
    if(korzen*2+2 < len(drzewo)):
        dfs_post(drzewo, korzen*2+2)
    if drzewo[korzen] != 0:
        print(drzewo[korzen], end=', ')
dfs_post(drzewo_binarne, 0)

Tomasz Walczak

Administrator

Dołączył: 2022-01-23

Liczba postów: 28

Odp: Drzewo

Drzewo - Literki

L to korzeń drzewa

L i R po lewej to instrukcje lewe dziecko, prawe dziecko
Litery wstawiamy w kolejnych poziomach