Obilazak stabla
<s>U informatici, pod obilaskom stabala smatra se proces posećivanja svakog čvora u stablu (struktura podataka), tačno jednom, sistematski.</s><s>Ovakvi obilasci se klasifikuju po redu u kojem su čvorovi posećeni.</s><s>Sledeći algoritmi su opisani za binarno stablo, ali mogu se generalizovati za ostala stabla, takođe.</s>

<s>Vrste 
U poređenju sa linearnim strukturama podataka kao što su povezane liste i jednodimenzionalnim nizovima, koji koriste kanonski metod obilaska, strukture stabala mogu se obići na mnogo različitih načina.</s><s>Počevši od korena binarnog stabla, postoje tri glavna koraka koja se mogu izvesti a red po kojem su izvedeni definiše vrstu obilaska.</s><s>Ovi koraci (bez nekog određenog reda) su: izvođenje akcije na trenutnom čvoru („posećivanje“ čvora), obilazak na levi sin čvora i obilazak na desni sin čvora.</s>

<s>Obilazak stabla prestavlja povezivanje svih čvorova u petlju na neki način.</s><s>Zato što od jednog datog čvora postoji više mogućih sledećih čvorova (to nije linearna struktura podataka), onda, kod sekvencijalnog računanja (ne paralelnog), neki čvorovi moraju biti odložen – skladišten na neki način da bi bio posećen posle.</s><s>Ovo se često radi preko steka (LIFO) ili reda (FIFO).</s><s>Kako je stablo samoreferencijalna (rekurzivno definisano) struktura podataka, obilazak se može objasniti kao rekurzija, ili korekurzija, u tom slučaju odloženi čvorovi se skladište „prećutno“, a u slučaju rekurzije u stek poziva.</s>

<s>Ime dato određenom stilu obilaska dolazi od reda kojim se čvorovi posećuju.</s><s>Najjednostavnije, da li jedan ide dole prvi ili preko prvo.</s><s>Obilazak u dubinu se dalje kvalifikuje po poziciji korenskog elementa sa obzirom na leve i desne čvorove.</s><s>Zamislite da su levi i desni čvorovi konstanta u prostoru, onda korenski čvor može biti postavljen sa leve strane levog čvora, između levog i desnog čvora, ili sa desne strane desnog čvora.</s><s>Ne postoji ekvivalent varijacija u obilasku u širinu – kada se gleda ređanje dece, obilazak u širinu je nedvosmislen.</s>

<s>Za svrhe ilustracije, smatra se da levi čvorovi uvek imaju prioritet u odnosu na desne čvorove.</s><s>Ređanje može biti i suprotno pod uslovom da se isto ređanje primenjuje za sve metode obilaska.</s>

<s>Obilazak u dubinu je lako primenljiv preko steka, uključujući i rekuzivno (preko kol steka), dok je obilazak u dubinu lako primenljiv preko reda, uključujući i korekurzivno.</s>

<s>Pored ovih osnovnih obilasaza, postoji mnogo kompleksnijih ili hibridnih šema, kao to su limitirane pretrage u dubinu i iterativne produbljujuće pretrage u dubinu.</s>

<s>Pretraga u dubinu</s>

<s>Postoje tri vrste obilazaka u dubinu: pre-order, in-order i post-order.</s><s>Za binarno stablo, oni su definisani kao rekurzivne operacije na svakom čvoru, počevši sa korenom čvora slede:</s>

<s>Preorder:
 „Poseta“ korenu
 Obilazak levog podstabla
 Oblazak desnog podstabla</s>

<s>Inorder (simetrično):
 Obilazak levog podstabla
 „Poseta“ korenu
 Obilazak desnog podstabla</s>

<s>Postorder:
 Obilazak levog podstabla
 Obilazak desnog podstabla
 „Poseta“ korenu</s>

<s>Trag obilaska se naziva sekvencijalizacija stabla.</s><s>Nijedna sekvencijalizacija prema pre-, in- ili post-order ne opisuje obilazak drveta jednistveno.</s><s>Ili pre-order ili post-order upareni sa in-orderom je dovoljna da se stablo opiše unikatno, dok pre-order sa post-orderom ostavlja neke dvosmislenosti u strukturi stabla.</s>

<s>Generičko stablo
Da bi obišao stablo u obilasku u dubinu, izvedite sledeće operacije rekurzivno na svakom čvoru:
 Izvesti preodrer operaciju
 for i=1 to n-1 do
 Poseti dete[i], if postoji
 Izvesti inorder operaciju
 Posetiti dete[n], if postoji
 Izvesti postorder operaciju</s>

<s>Gde je n broj čvorova dece.</s><s>U zavisnosti od datog problema, pre-order, in-order i post-order operacije mogu biti prazne, ili želite samo da posetite određen čvor, pa su ove operacije opcionalne.</s><s>Takođe, u praksi više od jedne pre, in i post-order operacije mogu biti potrebne.</s><s>Npr, prilikom unošenja u ternarno stablo, pre-order operacija se izvodi poređenjem elemenata.</s><s>Post-order operacije mogu biti potrebne kasnije da vrate stablo u ravnotežu.</s>

<s>Pretraga u širinu</s>

<s>Stabla mogu takođe biti obilažena po nivoima, gde se, pre prelaska na niži nivo, posećuje svaki čvor.</s>

<s>Upotreba</s>

<s>Pre-order obilasci prilikom dupliranja čvorova i vrednosti mogu napraviti kompletnu kopiju binarnog stabla.</s><s>Takođe se može koristiti za pravljenje prefiksnih izraza(Poljska notacija) iz stabala izraza: obilazak stabla izraza pre-orderski.</s>

<s>In-order obilaci se veoma često koriste za binarnu pretragu stabala, jer vraća vrednosti iz podvučenog seta po redu prema koji komparator postavlja u stablu za binarnu pretragu.</s>

<s>Post-order obilasci prilikom brisanja ili oslobađanja čvorova i vrednosti mogu izbrisati ili osloboditi celo binarno stablo.</s><s>Takođe, mogu generiati postfiksnu reprezentaciju binarnog stabla.</s>

<s>Primer</s>

<s>Binarno stablo:</s>

<s>Pretraga u dubinu
 Preorder sekvenca obilaska: F, B, A, D, C, E, G, I, H (koren, levo, desno) 
 Inorder sekvenca obilaska: A, B, C, D, E, F, G, H, I (levo, koren, desno) 
 Postorder sekvenca obilaska: A, C, E, D, B, H, I, G, F (levo, desno, koren)</s>

<s>Pretraga u širinu
 Sekvenca obilaska po nivoima: F, B, G, A, D, I, C, E, H</s>

<s>Implementacije</s>

<s>Pretraga u dubinu</s>

<s>Preorder</s>

<s>preorder(node)
   if node == null then return
   visit(node)
   preorder(node.left) 
   preorder(node.right)</s>

<s>iterativePreorder(node)
   parentStack = empty stack
   while not parentStack.isEmpty() or node != null
     if node != null then
       visit(node)
       parentStack.push(node.right)
       node = node.left
     else
       node = parentStack.pop()</s>

<s>Inorder</s>

<s>inorder(node)
   if node == null then return
   inorder(node.left)
   visit(node)
   inorder(node.right)</s>

<s>iterativeInorder(node)
   parentStack = empty stack
   while not parentStack.isEmpty() or node != null
     if node != null then
       parentStack.push(node)
       node = node.left
     else
       node = parentStack.pop()
       visit(node)
       node = node.right</s>

<s>Postorder 
 postorder(node)
   if node == null then return
   postorder(node.left)
   postorder(node.right)
   visit(node)</s>

<s>iterativePostorder(node)
   if node == null then return
   nodeStack.push(node)
   prevNode = null
   while not nodeStack.isEmpty()
     currNode = nodeStack.peek()
     if prevNode == null or prevNode.left == currNode or prevNode.right == currNode
       if currNode.left != null
         nodeStack.push(currNode.left)
       else if currNode.right != null
         nodeStack.push(currNode.right)
     else if currNode.left == prevNode
       if currNode.right != null
         nodeStack.push(currNode.right)
     else
       visit(currNode)
       nodeStack.pop()
     prevNode = currNode</s>

<s>Sve implementacije iznad zahtevaju prostor za poziv steka proporcijalan visini drveta.</s><s>U loše balansiranom stablu, ovo može biti bitno.</s><s>Možemo ukloniti potrebnost steka održavajući pokazivače u svakom čvoru, ili deljenjem stabla na niti.(sledeći deo)</s>

<s>Morisov inorder obilazak koristeći niti 
Binarno stablo je se deli na niti postavljanjem svakog pokazivača deteta da pokazuje na in-order prethodnik čvora i svaki desni pokazivač deteta da pokazuje na in-order sledbenika čvora.</s><s>Prednosti:
	Izbegava rekurzije, koje koriste kol stek i uzimaju memoriju i vreme
	Čvor čuva podatke roditelja
Nedostaci
	Stablo je kompleksnije
	Više je sklono greškama kada oba deteta nisu prikazana i obe vrednosti čvorova pokazuju na svoje pretke.</s><s>Morisov obilazak je implementacija in-order obilaska koji koristi niti:
	Kreira veza sa in-order sledbenikom
	Štampa podatke koristeći ove veze
	Vraća promene na originalno drvo</s>

<s>Pretraga u širinu</s>

<s>Takođe, ispod je naveden pseudokod za jednostavni obilazak nivoa zasnovan na redu i zahtevaće prostor proporcijalan maksimalnom broju čvorova na datoj širini.</s><s>Može biti jednak ukupnom broju čvorova / 2. Efikasniji po pitanju prostora pristup za ovu vrstu obilaska može biti implementiran koristeći iterativnu produbljujuću pretragu u dubinu(iterative deepening depth-first search).</s>

<s>levelorder(root)
   q = empty queue
   q.enqueue(root)
   while not q.empty do
     node := q.dequeue()
     visit(node)
     if node.left ≠ null
       q.enqueue(node.left)
     if node.right ≠ null
       q.enqueue(node.right)</s>

<s>Beskonačna stabla</s>

<s>Iako se obilasci obično rade za stabla sa ograničenim brojem članova, mogu biti urađeni i sa beskonačnim stablima.</s><s>Ovo je od posebnog značaja za funkcionalno programiranje, kako se beskonačne strukture podataka mogu često lako definisati i raditi, iako nisu ocenjene, ovo bi uzelo beskonačno mnogo vremena.</s><s>Neka stabla ograničenim brojem članova su prevelika za reprezentaciju, kao što su stablo igre za šah, tako da je korisno analizirati ih kao da su beskonačna.</s>

<s>Osnovna potreba obilaska je posećivanje svakog čvora.</s><s>Za beskonačna stabla, jednostavni algoritmi često ne uspeju ovo da urade.</s><s>Npr, kada je dato binarno stablo beskonačne dubine, obilazak u dubinu će ići nadole po jednoj strani stabla, nikad ne posećivajući ostatak, i in i post-order neće nikada posetiti nijedan član, jer nije dostigao list.</s><s>Obilazak u širinu, po nivoima, će obići binarno stablo beskonačne dubine bez problema, i stvarno će obići svako vezano stablo.</s>

<s>Sa druge strane, ako je dato stablo dubine 2, gde korenski član ima beskonačno mnogo dece, i svako od te dece ima dvoje dece, obilazak u dubinu će obići sve čvorove, kada iscrpi unuke, on će preći na sledeće.</s><s>Dok kod obilazaka u širinu, nikada neće doći do unuka, zato što će pokušavati da iscrpi svu decu prvo.</s>

<s>Sofiticiranija analiza može se ostvariti preko beskonačnih rednih brojeva: npr, obilazak u širniu dubine 2 stabla iznad će uzeti ?· dva koraka ? za prvi nivo, a drugi ? za drugi nivo.</s>

<s>Jednostavne pretrage obilazaka u dubinu i širinu ne obiđu svako beskonačno stablo, i nisu tako efikasni na veoma velikim stablima.</s><s>Ipak, hibridne metode obići svako beskonačno stablo, esencijalno preko diagonalnog argumenta (diagonalno – kombinacija vertikalnog i horizontalnog – odgovara kombinaciji dubine i širine).</s>

<s>Konkretno, uzevši granajuće beskonačno stablo beskonačne dubine, označavamo koren , decu čvora a unuke čvora  i tako dalje.</s><s>Članovi su 1-1(bijekcija) sa određenim sekvencama pozitivnih brojeva, koji su brojivi i mogu biti postavljeni u red prvo po broju ulaza, a zatim i leksikografskim redom uzevši u obzir dati broj ulaza, koji daju obilazak.</s><s>Eksplicitno:</s>

<s>0: ()
 1: (1)
 2: (1,1) (2)
 3: (1,1,1) (1,2) (2,1) (3)
 4: (1,1,1,1) (1,1,2) (1,2,1) (1,3) (2,1,1) (2,2) (3,1) (4)</s>

<s>itd.</s>

<s>Ovo može biti tumačeno kao unošenja na mapu binarnog stabla beskonačne dubine na ovo stablo i onda primenjivanje obilaska u širinu.</s><s>Zameniti donje ivice povezivanjem roditeljskog člana na njegov sledeči a zatim dete sa desnim ivicama prvogd deteta sa drugim, drugog sa trećim i tako danja.</s><s>Iako svakim korako može ići ili dole ili levo, koji pokazuje odnose između beskonačnog binarnog stabla i numerisanja odozgo; suma svih ulaza odgovara distanci od korena, koji odgovara 2n-1 na dubini n-1 u beskonačnom binarnom stablu.</s>

<s>Reference</s>

<s>Literatura 
 Dale, Nell.</s><s>Lilly, Susan D. "Pascal Plus Data Structures".</s><s>D. C. Heath and Company.</s><s>Lexington, MA.</s><s>1995.</s><s>Fourth Edition.</s><s>Drozdek, Adam.</s><s>"Data Structures and Algorithms in C++".</s><s>Brook/Cole.</s><s>Pacific Grove, CA.</s><s>2001.</s><s>Second edition.
 http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran</s>

<s>Spoljašnje veze</s>

<s>Animation Applet of Binary Tree Traversal
 The Adjacency List Model for Processing Trees with SQL 
 Storing Hierarchical Data in a Database with traversal examples in PHP
 Managing Hierarchical Data in MySQL
 Working with Graphs in MySQL
 Non-recursive traversal of DOM trees in JavaScript 
 Sample code for recursive and iterative tree traversal implemented in C.
 Sample code for recursive tree traversal in C#.</s><s>See tree traversal implemented in various programming language on Rosetta Code
 Tree traversal without recursion</s>

<s>Stabla (strukture podataka)
Algoritmi
Rekurzije</s>

