==== BINARNO STABLO ==== **Binarno stablo** je specijalni slučaj stabla u kome ni jedan čvor nema stepen veći od 2. To praktično znači da svaki čvor ima najviše dva naslednika. Dakle, binarno stablo je skup od jednog ili više čvorova takvih da:\\ - Postoji jedan čvor koji je koren stabla i\\ - Preostali čvorovi su podeljeni u dva disjunktna skupa, tako da svaki skup predstavlja binarno stablo. Ova dva skupa se nazivaju levo i desno podstablo.\\ Za binarno stablo važi:\\ - Maksimalni broj čvorova na i-tom nivou je 2i−1\\ - Ako je k dubina binarnog stabla, onda je maksimalan broj čvorova koje stablo može da ima je: 2k − 1 = 2k −1 + 2k − 2 + ... + 20\\ Puno binarno stablo je binarno stablo dubine k koje sadrži 2k − 1 čvorova. Ukoliko je broj čvorova manji od 2k − 1 , binarno stablo je nepotpuno.\\ **Kompletno binarno stablo** dubine k je stablo sa n čvorova u kome bi se ovih n čvorova moglo numerisati brojevima od 1 do n, kao kada bi to bilo prvih n čvorova u punom stablu dubine k.\\ **Obilazak binarnog stabla**\\ Pod obilaskom binarnog stabla podrazumevamo prolazak kroz sve njegove čvorove određenim redosledom, pri čemu je istovremeno moguće izvršiti i određenu operaciju nad podacima koji su u njima zapisani.\\ U zavisnosti od redosleda obrade određenog čvora i njegovog levog i desnog podstabla, obilazak stabla se može izvršiti na šest načina:\\ * **LPD** obilazak levog podstabla, obrada podatka, obilazak desnog podstabla\\ * **LDP** obilazak levog podstabla, obilazak desnog podstabla, obrada podatka\\ * **PLD** obrada podatka, obilazak levog podstabla, obilazak desnog podstabla\\ * **PDL** obrada podatka, obilazak desnog podstabla, obilazak levog podstabla\\ * **DLP** obilazak desnog podstabla, obilazak levog podstabla, obrada podatka\\ * **DPL** obilazak desnog podstabla, obrada podatka, obilazak levog podstabla\\ pri čemu:\\ **L** – označava obilazak levog podstabla,\\ **D** – označava obilazak desnog podstabla,\\ **P** – označava obradu podatka u trenutnom čvoru.\\ Tako, na primer LPD označava redosled u kome krećemo od korena, obilazimo levo podstablo, obrađujemo podatak u korenu i na kraju obilazimo desno podstablo. S obzirom na to da su levo i desno podstablo takođe binarna stabla, potpuno ista procedura se koristi i za njihov obilazak.\\ Redosled LPD se naziva još i inorder, redosled LDP postorder, a redosled PLD preorder. Ostala tri redosleda se nikada ne koriste.\\