*Implementacija z dvojiškim iskalnim drevesom

Dvojiško drevo lahko v pythonu predstavimo podobno kot povezani seznam: s tabelo vozlišč. Vozlišče na indeksu 0 (glava) je predstavljeno s tabelo, ki vsebuje število elementov in indeks korena drevesa, vsa ostala vozlišča pa so predstavljena s tabelami, ki vsebujejo element v vozlišču ter indeksa njegovega levega in desnega naslednika. Kot neveljaven indeks lahko ponovno uporabimo število 0. Podobno kot pri povezanem seznamu so lahko vozlišča v tabeli nanizana v poljubnem vrstnem redu; pomembno je le, da so med seboj pravilno povezana z indeksi. Oglejmo si primer:

Zgornja tabela je v pythonu predstavljena tako:

drevo = [[7, 1], [20, 2, 6], [10, 3, 4],
         [7, 0, 0], [15, 5, 0], [12, 0, 0],
         [30, 0, 7], [35, 0, 0]]

Radovedni si lahko ogledate modul mnozicaIskalnoDrevo.py, v katerem so implementirane operacije Ustvari, JePrisoten in Dodaj:

# Implementacija množice z dvojiškim iskalnim # drevesom. # Vrne prazno množico. def Ustvari(): return [[0, 0]] # Vrne True, če je podani element prisoten v # podani množici, sicer pa vrne False. def JePrisoten(mnozica, element): # Pričnemo v korenu drevesa. indeksVozlisca = mnozica[0][1] # Vsakokrat se pomaknemo v levega oziroma # desnega naslednika trenutnega vozlišča, # odvisno od elementa v trenutnem vozlišču. while (indeksVozlisca > 0 and mnozica[indeksVozlisca][0] != element): if element < mnozica[indeksVozlisca][0]: indeksVozlisca = mnozica[indeksVozlisca][1] else: indeksVozlisca = mnozica[indeksVozlisca][2] # Postopek se lahko konča v vozlišču, ki # vsebuje element, ali pa pri indeksu 0 (v tem # primeru vemo, da drevo ne vsebuje iskanega # elementa). return (indeksVozlisca > 0) # Doda podani element v podano množico. def Dodaj(mnozica, element): if mnozica[0][0] == 0: # poseben primer: dodajanje v prazno drevo indeksDodanegaVozlisca = len(mnozica) mnozica.append([element, 0, 0]) mnozica[0][1] = indeksDodanegaVozlisca mnozica[0][0] += 1 return # Poiščemo indeks vozlišča, na katerega bomo # povezali novo vozlišče. indeksPredhodnika = 0 indeksVozlisca = mnozica[0][1] while indeksVozlisca > 0: indeksPredhodnika = indeksVozlisca if element == mnozica[indeksVozlisca][0]: # Element v drevesu že obstaja, zato # predčasno končamo. return elif element < mnozica[indeksVozlisca][0]: indeksVozlisca = mnozica[indeksVozlisca][1] else: indeksVozlisca = mnozica[indeksVozlisca][2] # Novo vozlišče dodamo na konec tabele, ki # predstavlja drevo, in ga povežemo z # njegovim predhodnikom. indeksDodanegaVozlisca = len(mnozica) mnozica.append([element, 0, 0]) if element > mnozica[indeksPredhodnika][0]: # Novo vozlišče postane desni naslednik # svojega predhodnika. mnozica[indeksPredhodnika][2] = \ indeksDodanegaVozlisca else: # Novo vozlišče postane levi naslednik # svojega predhodnika. mnozica[indeksPredhodnika][1] = \ indeksDodanegaVozlisca # Število elementov v drevesu se poveča za 1. mnozica[0][0] += 1 def main(): t = [10, 5, 15, 18, 9, 17, 12, 7] print('Ustvarjam prazno množico m ...') m = Ustvari() for element in t: print('Dodajam element: ' + str(element)) Dodaj(m, element) print('JePrisoten(m, 3): ' + str(JePrisoten(m, 3))) print('JePrisoten(m, 5): ' + str(JePrisoten(m, 5))) print('JePrisoten(m, 6): ' + str(JePrisoten(m, 6))) print('JePrisoten(m, 7): ' + str(JePrisoten(m, 7))) print('Tabela vozlišč, ki predstavljajo m:') print(m) if __name__ == '__main__': main()

Izvedi Počisti