Binarna Stabla
Binarno stablo je struktura podataka u kojoj svaki čvor (Node) ili vrh (Leaf) ima najviše dve grane (Branch). U Python-u, binarno stablo može biti predstavljeno na različite načine sa različitim strukturama podataka i prikazima klasa za čvor. Biblioteka binarnog stabla pomaže u direktnoj implementaciji binarnog stabla i importuje sa sledećim kodom:
pip install binarytree
Da bi se realizovalo jedno binarno stablo u python-u, na samom početku je potrebno uvesti samu biblioteku koju ste prethodno instalirali u svom projektu i povući sve funkcije koje se nalaze u toj biblioteci
from binarytree import *
Na ovaj način ste uvezli sve potrebne funkcije od kojih su [ Node, build, tree]. Node funkciju ćemo koristiti za konkretno definisanje Node-a, odnosno čvora jednog stabla. Build se koristi da bi se kreiralo stablo od niza podataka i tree za kreiranje nasumičnih vrednosti stabla sa dodatnim specifikacijama koji se mogu dodatno definisati. O ovim funkcijama će detaljno biti rečeno u narednom delu stranice.
Node se koristi za kreiranje svakog zasebnog čvora stabla. Za dodelu vrednosti jednog node-a mora se pre toga definisati "koren" tj root čvor kao početak stabla. Na taj root node se kasnije dodaju dodatni čvorovi koji su kategorizovani kao leva strana (left) i desna strana (right), na kojima se opet mogu dodavati isti itd. Primer kako bi se kreiralo jedno stablo na ovaj način je:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.right.left = Node(8)
print('Binary tree :', root)
Output:
Binary tree :
_1__
/ \
2 3__
/ \ / \
4 5 6 7
/
8
Build funkciju koristimo kada želimo da generišemo binarno stablo od niza podataka. Kada se stablo generiše ono teži da kreira "savršeno" stablo, odnosno da svaki čvor ima levu i desnu stranu. Ukoliko želimo da ne doda čvor, koristimo reč None, ali imajući u vidu da ako kroz generisanje stabla naiđemo na taj čvor, nije moguće dodati na njega dalji čvor. Generisanje stabla se vrši redom, sa leva na desno kroz svaki red redom. Primer koda je sledeći:
nodes = [1, 2, 3, 4, 5, 6, 7, None, 9, 10]
root = build(nodes)
print('Binary tree :', root)
Output:
Binary tree :
____1___
/ \
__2___ 3
/ \ / \
4 _5 6 7
\ /
9 10
Tree funkcija se koristi za random generisanje stabla sa posebnim opcijama koje možemo sami definisati. Kod pomocu kojeg to možemo uraditi je:
root = tree(height = 4, is_perfect = True)
U ovom delu smo kreirali nasumično stablo sa 4 nivoa (ne računajući root), i osobinom da bude "savršeno", što znači da svaki čvor ima levi i desni čvor ne računajući one u 4tom nivou. Rezultat pokretanja koda je sledeći:
Output:
Binary tree :
____________________10__________________
_________27________ ________5________
/ \ / \
__28___ ___12___ ___9__ ___13__
/ \ / \ / \ / \
_1 _20 _29 _23 _11 24 _18 14
/ \ / \ / \ / \ / \ / \ / \ / \
30 7 22 4 26 8 17 19 21 6 3 15 25 0 2 16
Sada kada znamo sve ove načine kako formirati stablo moramo znati i kako da predstavimo rezultate u terminalu. Prvi deo je već bio predstavljen gde se samo ispisuje stablo u terminalu i "slikovitom" prikazu. Da bi se lakše predstavili čvorovi stabla postoje tri različita načina sortiranja čvorova pri njihovom ispisu u terminalu. Ta tri tipa sortiranja su:
Preorder Traversal - Način sortiranja koji ispisuje čvorove krenuvši od koren čvora pa redom na levu stranu. Kada se dodje do kraja leve strane, vraća se u jedan čvor unazad pa se ispituje čvor sa desne strane, kada se tu dodje do kraja, opet se vraća polje unazad pa ispituje desni čvor i sve tako dok se ne ispišu svi čvorovi stabla. Ovaj stil sortiranja se drugačije naziva i pretraga stabla u dubinu.
Inorder Traversal - Ovaj tip sortiranja je teško definisati kada koristik ispisuje čvorove na listu papira. Rezultat ovog sortiranja se dobija kada se na stablo ispisuju vizuelno redom čvorovi sa leva na desno tako kako su predstavljeni u temrinalu.
Postorder Traversal - Ovaj tip sortiranja se gleda tako što se gledajući sa leva na desno ispisuju svi čvorovi koji pripadaju čvoru koje oni nasleđuju. Kada se ispišu svi ti čvorovi onda se na isti način gleda čvor koji su nasledili.
Jednostavan print - Ovo u suštini nije sortiranje nego jednostavan ispis svih čvorova pomoću liste. Ispisuje se tako što se gledajući sa leva na desno ispisuju redom svi čvorovi redom po novoima. Ovaj tip ispisa drugačije naziva pretraga u širinu.
Stablo :
_____12________
/ \
___3__ ___7___
/ \ / \
6 5 _14 _9
/ \ / \ / \ / \
8 10 0 2 11 4 13 1
Lista : 12, 3, 7, 6, 5, 14, 9, 8, 10, 0, 2, 11, 4, 13, 1
Preorder : 12, 3, 6, 8, 10, 5, 0, 2, 7, 14, 11, 4, 9, 13, 1
Inorder : 8, 6, 10, 3, 0, 5, 2, 12, 11, 14, 4, 7, 13, 9, 1
Postorder : 8, 10, 6, 0, 2, 5, 3, 11, 4, 14, 13, 1, 9, 7, 12
Uz običan ispis samih čvorova se dodatno može ispisati i specifikacija samog stabla. Neki od tih specifikacija su:
.size - Metoda koja ispisuje broj čvorova stabla.
.height - Metoda koja ispisuje broj nivoa stabla.
.leaf_count - Metoda za ispis koliko lista (leaf) sadrži stablo.
.leaves - Metoda za ispis svih lista stabla.
Postoje još mnogo drugih metoda koje se mogu koristiti. Za širi ispis većine korisnih informacija jednog stabla se koristi .properties metoda.
Invertovanje binarnog stabla (engl. binary tree inversion) je proces zamene levičastih i desničastih podstabala svakog čvora u binarnom stablu. To rezultira promenom strukture stabla, tako da se leva podstabla pretvaraju u desna, a sva desna podstabla postaju leva kao na datom primeru.
Output:
__1__
/ \
2 3
/ \ / \
4 5 6 7
__1__
/ \
3 2
/ \ / \
7 6 5 4