Обилазак стабла
У информатици, под обиласком стабала сматра се процес посећивања сваког чвора у стаблу (структура података), тачно једном, систематски. Овакви обиласци се класификују по реду у којем су чворови посећени. Следећи алгоритми су описани за бинарно стабло, али могу се генерализовати за остала стабла, такође.

Врсте 
У поређењу са линеарним структурама података као што су повезане листе и једнодимензионалним низовима, који користе канонски метод обиласка, структуре стабала могу се обићи на много различитих начина. Почевши од корена бинарног стабла, постоје три главна корака која се могу извести а ред по којем су изведени дефинише врсту обиласка. Ови кораци (без неког одређеног реда) су: извођење акције на тренутном чвору („посећивање“ чвора), обилазак на леви син чвора и обилазак на десни син чвора.

Обилазак стабла преставља повезивање свих чворова у петљу на неки начин. Зато што од једног датог чвора постоји више могућих следећих чворова (то није линеарна структура података), онда, код секвенцијалног рачунања (не паралелног), неки чворови морају бити одложен – складиштен на неки начин да би био посећен после. Ово се често ради преко стека (ЛИФО) или реда (ФИФО). Како је стабло самореференцијална (рекурзивно дефинисано) структура података, обилазак се може објаснити као рекурзија, или корекурзија, у том случају одложени чворови се складиште „прећутно“, а у случају рекурзије у стек позива.

Име дато одређеном стилу обиласка долази од реда којим се чворови посећују. Најједноставније, да ли један иде доле први или преко прво. Обилазак у дубину се даље квалификује по позицији коренског елемента с обзиром на леве и десне чворове. Замислите да су леви и десни чворови константа у простору, онда коренски чвор може бити постављен са леве стране левог чвора, између левог и десног чвора, или са десне стране десног чвора. Не постоји еквивалент варијација у обиласку у ширину – када се гледа ређање деце, обилазак у ширину је недвосмислен.

За сврхе илустрације, сматра се да леви чворови увек имају приоритет у односу на десне чворове. Ређање може бити и супротно под условом да се исто ређање примењује за све методе обиласка.

Обилазак у дубину је лако применљив преко стека, укључујући и рекузивно (преко кол стека), док је обилазак у дубину лако применљив преко реда, укључујући и корекурзивно.

Поред ових основних обиласаза, постоји много комплекснијих или хибридних шема, као то су лимитиране претраге у дубину и итеративне продубљујуће претраге у дубину.

Претрага у дубину 

Постоје три врсте обилазака у дубину: пре-ордер, ин-ордер и пост-ордер. За бинарно стабло, они су дефинисани као рекурзивне операције на сваком чвору, почевши са кореном чвора следе:

Преордер:
 „Посета“ корену
 Обилазак левог подстабла
 Облазак десног подстабла

Инордер (симетрично):
 Обилазак левог подстабла
 „Посета“ корену
 Обилазак десног подстабла

Постордер:
 Обилазак левог подстабла
 Обилазак десног подстабла
 „Посета“ корену

Траг обиласка се назива секвенцијализација стабла. Ниједна секвенцијализација према пре-, ин- или пост-ордер не описује обилазак дрвета једниствено. Или пре-ордер или пост-ордер упарени са ин-ордером је довољна да се стабло опише уникатно, док пре-ордер са пост-ордером оставља неке двосмислености у структури стабла.

Генеричко стабло
Да би обишао стабло у обиласку у дубину, изведите следеће операције рекурзивно на сваком чвору:
 Извести преодрер операцију
 for i=1 to n-1 do
 Посети дете[i], if постоји
 Извести инордер операцију
 Посетити дете[n], if постоји
 Извести постордер операцију

Где је n број чворова деце. У зависности од датог проблема, пре-ордер, ин-ордер и пост-ордер операције могу бити празне, или желите само да посетите одређен чвор, па су ове операције опционалне. Такође, у пракси више од једне пре, ин и пост-ордер операције могу бити потребне. Нпр, приликом уношења у тернарно стабло, пре-ордер операција се изводи поређењем елемената. Пост-ордер операције могу бити потребне касније да врате стабло у равнотежу.

Претрага у ширину 

Стабла могу такође бити обилажена по нивоима, где се, пре преласка на нижи ниво, посећује сваки чвор.

Употреба 

Пре-ордер обиласци приликом дуплирања чворова и вредности могу направити комплетну копију бинарног стабла. Такође се може користити за прављење префиксних израза (Пољска нотација) из стабала израза: обилазак стабла израза пре-ордерски.

Ин-ордер обилаци се веома често користе за бинарну претрагу стабала, јер враћа вредности из подвученог сета по реду према који компаратор поставља у стаблу за бинарну претрагу.

Пост-ордер обиласци приликом брисања или ослобађања чворова и вредности могу избрисати или ослободити цело бинарно стабло. Такође, могу генериати постфиксну репрезентацију бинарног стабла.

Пример 

Бинарно стабло:

Претрага у дубину
 Преордер секвенца обиласка: F, B, A, D, C, E, G, I, H (корен, лево, десно) 
 Инордер секвенца обиласка: A, B, C, D, E, F, G, H, I (лево, корен, десно) 
 Постордер секвенца обиласка: A, C, E, D, B, H, I, G, F (лево, десно, корен) 

Претрага у ширину
 Секвенца обиласка по нивоима: F, B, G, A, D, I, C, E, H

Имплементације

Претрага у дубину

Преордер 

 preorder(node)
   if node == null then return
   visit(node)
   preorder(node.left) 
   preorder(node.right)

 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()

Инордер 

 inorder(node)
   if node == null then return
   inorder(node.left)
   visit(node)
   inorder(node.right)

 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

Постордер 
 postorder(node)
   if node == null then return
   postorder(node.left)
   postorder(node.right)
   visit(node)

 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

Све имплементације изнад захтевају простор за позив стека пропорцијалан висини дрвета. У лоше балансираном стаблу, ово може бити битно. Можемо уклонити потребност стека одржавајући показиваче у сваком чвору, или дељењем стабла на нити.(следећи део)

Морисов инордер обилазак користећи нити 
Бинарно стабло је се дели на нити постављањем сваког показивача детета да показује на ин-ордер претходник чвора и сваки десни показивач детета да показује на ин-ордер следбеника чвора. Предности:
	Избегава рекурзије, које користе кол стек и узимају меморију и време
	Чвор чува податке родитеља
Недостаци
	Стабло је комплексније
	Више је склоно грешкама када оба детета нису приказана и обе вредности чворова показују на своје претке.
Морисов обилазак је имплементација ин-ордер обиласка који користи нити:
	Креира веза са ин-ордер следбеником
	Штампа податке користећи ове везе
	Враћа промене на оригинално дрво

Претрага у ширину 

Такође, испод је наведен псеудокод за једноставни обилазак нивоа заснован на реду и захтеваће простор пропорцијалан максималном броју чворова на датој ширини. Може бити једнак укупном броју чворова / 2. Ефикаснији по питању простора приступ за ову врсту обиласка може бити имплементиран користећи итеративну продубљујућу претрагу у дубину(iterative deepening depth-first search).

 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)

Бесконачна стабла 

Иако се обиласци обично раде за стабла са ограниченим бројем чланова, могу бити урађени и са бесконачним стаблима. Ово је од посебног значаја за функционално програмирање, како се бесконачне структуре података могу често лако дефинисати и радити, иако нису оцењене, ово би узело бесконачно много времена. Нека стабла ограниченим бројем чланова су превелика за репрезентацију, као што су стабло игре за шах, тако да је корисно анализирати их као да су бесконачна.

Основна потреба обиласка је посећивање сваког чвора. За бесконачна стабла, једноставни алгоритми често не успеју ово да ураде. Нпр, када је дато бинарно стабло бесконачне дубине, обилазак у дубину ће ићи надоле по једној страни стабла, никад не посећивајући остатак, и ин и пост-ордер неће никада посетити ниједан члан, јер није достигао лист. Обилазак у ширину, по нивоима, ће обићи бинарно стабло бесконачне дубине без проблема, и стварно ће обићи свако везано стабло.

Са друге стране, ако је дато стабло дубине 2, где коренски члан има бесконачно много деце, и свако од те деце има двоје деце, обилазак у дубину ће обићи све чворове, када исцрпи унуке, он ће прећи на следеће. Док код обилазака у ширину, никада неће доћи до унука, зато што ће покушавати да исцрпи сву децу прво.

Софитициранија анализа може се остварити преко бесконачних редних бројева: нпр, обилазак у ширниу дубине 2 стабла изнад ће узети ?· два корака ? за први ниво, а други ? за други ниво.

Једноставне претраге обилазака у дубину и ширину не обиђу свако бесконачно стабло, и нису тако ефикасни на веома великим стаблима. Ипак, хибридне методе обићи свако бесконачно стабло, есенцијално преко диагоналног аргумента (диагонално – комбинација вертикалног и хоризонталног – одговара комбинацији дубине и ширине).

Конкретно, узевши гранајуће бесконачно стабло бесконачне дубине, означавамо корен , децу чвора а унуке чвора  и тако даље. Чланови су 1-1(бијекција) са одређеним секвенцама позитивних бројева, који су бројиви и могу бити постављени у ред прво по броју улаза, а затим и лексикографским редом узевши у обзир дати број улаза, који дају обилазак. Експлицитно:

 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)

итд.

Ово може бити тумачено као уношења на мапу бинарног стабла бесконачне дубине на ово стабло и онда примењивање обиласка у ширину. Заменити доње ивице повезивањем родитељског члана на његов следечи а затим дете са десним ивицама првогд детета са другим, другог са трећим и тако дања. Иако сваким корако може ићи или доле или лево, који показује односе између бесконачног бинарног стабла и нумерисања одозго; сума свих улаза одговара дистанци од корена, који одговара 2н-1 на дубини н-1 у бесконачном бинарном стаблу.

Референце

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

Спољашње везе 

 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#. 
 See tree traversal implemented in various programming language on Rosetta Code
 Tree traversal without recursion

Стабла (структуре података)
Алгоритми
Рекурзије
У информатици , под обиласком стабала сматра се процес посећивања сваког чвора у стаблу ( структура података ) , тачно једном , систематски . Овакви обиласци се класификују по реду у којем су чворови посећени . Следећи алгоритми су описани за бинарно стабло , али могу се генерализовати за остала стабла , такође . Врсте У поређењу са линеарним структурама података као што су повезане листе и једнодимензионалним низовима , који користе канонски метод обиласка , структуре стабала могу се обићи на много различитих начина . Почевши од корена бинарног стабла , постоје три главна корака која се могу извести а ред по којем су изведени дефинише врсту обиласка . Ови кораци ( без неког одређеног реда ) су : извођење акције на тренутном чвору ( „ посећивање “ чвора ) , обилазак на леви син чвора и обилазак на десни син чвора . Обилазак стабла преставља повезивање свих чворова у петљу на неки начин . Зато што од једног датог чвора постоји више могућих следећих чворова ( то није линеарна структура података ) , онда , код секвенцијалног рачунања ( не паралелног ) , неки чворови морају бити одложен – складиштен на неки начин да би био посећен после . Ово се често ради преко стека ( ЛИФО ) или реда ( ФИФО ) . Како је стабло самореференцијална ( рекурзивно дефинисано ) структура података , обилазак се може објаснити као рекурзија , или корекурзија , у том случају одложени чворови се складиште „ прећутно “ , а у случају рекурзије у стек позива . Име дато одређеном стилу обиласка долази од реда којим се чворови посећују . Најједноставније , да ли један иде доле први или преко прво . Обилазак у дубину се даље квалификује по позицији коренског елемента с обзиром на леве и десне чворове . Замислите да су леви и десни чворови константа у простору , онда коренски чвор може бити постављен са леве стране левог чвора , између левог и десног чвора , или са десне стране десног чвора . Не постоји еквивалент варијација у обиласку у ширину – када се гледа ређање деце , обилазак у ширину је недвосмислен . За сврхе илустрације , сматра се да леви чворови увек имају приоритет у односу на десне чворове . Ређање може бити и супротно под условом да се исто ређање примењује за све методе обиласка . Обилазак у дубину је лако применљив преко стека , укључујући и рекузивно ( преко кол стека ) , док је обилазак у дубину лако применљив преко реда , укључујући и корекурзивно . Поред ових основних обиласаза , постоји много комплекснијих или хибридних шема , као то су лимитиране претраге у дубину и итеративне продубљујуће претраге у дубину . Претрага у дубину Постоје три врсте обилазака у дубину : пре-ордер , ин-ордер и пост-ордер . За бинарно стабло , они су дефинисани као рекурзивне операције на сваком чвору , почевши са кореном чвора следе : Преордер : „ Посета “ корену Обилазак левог подстабла Облазак десног подстабла Инордер ( симетрично ) : Обилазак левог подстабла „ Посета “ корену Обилазак десног подстабла Постордер : Обилазак левог подстабла Обилазак десног подстабла „ Посета “ корену Траг обиласка се назива секвенцијализација стабла . Ниједна секвенцијализација према пре- , ин- или пост-ордер не описује обилазак дрвета једниствено . Или пре-ордер или пост-ордер упарени са ин-ордером је довољна да се стабло опише уникатно , док пре-ордер са пост-ордером оставља неке двосмислености у структури стабла . Генеричко стабло Да би обишао стабло у обиласку у дубину , изведите следеће операције рекурзивно на сваком чвору : Извести преодрер операцију for i=1 to n-1 do Посети дете[ i ] , if постоји Извести инордер операцију Посетити дете[ n ] , if постоји Извести постордер операцију Где је n број чворова деце . У зависности од датог проблема , пре-ордер , ин-ордер и пост-ордер операције могу бити празне , или желите само да посетите одређен чвор , па су ове операције опционалне . Такође , у пракси више од једне пре , ин и пост-ордер операције могу бити потребне . Нпр , приликом уношења у тернарно стабло , пре-ордер операција се изводи поређењем елемената . Пост-ордер операције могу бити потребне касније да врате стабло у равнотежу . Претрага у ширину Стабла могу такође бити обилажена по нивоима , где се , пре преласка на нижи ниво , посећује сваки чвор . Употреба Пре-ордер обиласци приликом дуплирања чворова и вредности могу направити комплетну копију бинарног стабла . Такође се може користити за прављење префиксних израза ( Пољска нотација ) из стабала израза : обилазак стабла израза пре-ордерски . Ин-ордер обилаци се веома често користе за бинарну претрагу стабала , јер враћа вредности из подвученог сета по реду према који компаратор поставља у стаблу за бинарну претрагу . Пост-ордер обиласци приликом брисања или ослобађања чворова и вредности могу избрисати или ослободити цело бинарно стабло . Такође , могу генериати постфиксну репрезентацију бинарног стабла . Пример Бинарно стабло : Претрага у дубину Преордер секвенца обиласка : F , B , A , D , C , E , G , I , H ( корен , лево , десно ) Инордер секвенца обиласка : A , B , C , D , E , F , G , H , I ( лево , корен , десно ) Постордер секвенца обиласка : A , C , E , D , B , H , I , G , F ( лево , десно , корен ) Претрага у ширину Секвенца обиласка по нивоима : F , B , G , A , D , I , C , E , H Имплементације Претрага у дубину Преордер preorder( node ) if node == null then return visit( node ) preorder( node.left ) preorder( node.right ) 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 ( ) Инордер inorder( node ) if node == null then return inorder( node.left ) visit( node ) inorder( node.right ) 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 Постордер postorder( node ) if node == null then return postorder( node.left ) postorder( node.right ) visit( node ) 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 Све имплементације изнад захтевају простор за позив стека пропорцијалан висини дрвета . У лоше балансираном стаблу , ово може бити битно . Можемо уклонити потребност стека одржавајући показиваче у сваком чвору , или дељењем стабла на нити.( следећи део ) Морисов инордер обилазак користећи нити Бинарно стабло је се дели на нити постављањем сваког показивача детета да показује на ин-ордер претходник чвора и сваки десни показивач детета да показује на ин-ордер следбеника чвора . Предности : Избегава рекурзије , које користе кол стек и узимају меморију и време Чвор чува податке родитеља Недостаци Стабло је комплексније Више је склоно грешкама када оба детета нису приказана и обе вредности чворова показују на своје претке . Морисов обилазак је имплементација ин-ордер обиласка који користи нити : Креира веза са ин-ордер следбеником Штампа податке користећи ове везе Враћа промене на оригинално дрво Претрага у ширину Такође , испод је наведен псеудокод за једноставни обилазак нивоа заснован на реду и захтеваће простор пропорцијалан максималном броју чворова на датој ширини . Може бити једнак укупном броју чворова / Ефикаснији по питању простора приступ за ову врсту обиласка може бити имплементиран користећи итеративну продубљујућу претрагу у дубину( iterative deepening depth-first search ). 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 ) Бесконачна стабла Иако се обиласци обично раде за стабла са ограниченим бројем чланова , могу бити урађени и са бесконачним стаблима . Ово је од посебног значаја за функционално програмирање , како се бесконачне структуре података могу често лако дефинисати и радити , иако нису оцењене , ово би узело бесконачно много времена . Нека стабла ограниченим бројем чланова су превелика за репрезентацију , као што су стабло игре за шах , тако да је корисно анализирати их као да су бесконачна . Основна потреба обиласка је посећивање сваког чвора . За бесконачна стабла , једноставни алгоритми често не успеју ово да ураде . Нпр , када је дато бинарно стабло бесконачне дубине , обилазак у дубину ће ићи надоле по једној страни стабла , никад не посећивајући остатак , и ин и пост-ордер неће никада посетити ниједан члан , јер није достигао лист . Обилазак у ширину , по нивоима , ће обићи бинарно стабло бесконачне дубине без проблема , и стварно ће обићи свако везано стабло . Са друге стране , ако је дато стабло дубине где коренски члан има бесконачно много деце , и свако од те деце има двоје деце , обилазак у дубину ће обићи све чворове , када исцрпи унуке , он ће прећи на следеће . Док код обилазака у ширину , никада неће доћи до унука , зато што ће покушавати да исцрпи сву децу прво . Софитициранија анализа може се остварити преко бесконачних редних бројева : нпр , обилазак у ширниу дубинестабла изнад ће узети ? · два корака ? за први ниво , а други ? за други ниво . Једноставне претраге обилазака у дубину и ширину не обиђу свако бесконачно стабло , и нису тако ефикасни на веома великим стаблима . Ипак , хибридне методе обићи свако бесконачно стабло , есенцијално преко диагоналног аргумента ( диагонално – комбинација вертикалног и хоризонталног – одговара комбинацији дубине и ширине ) . Конкретно , узевши гранајуће бесконачно стабло бесконачне дубине , означавамо корен , децу чвора а унуке чвора и тако даље . Чланови субијекција ) са одређеним секвенцама позитивних бројева , који су бројиви и могу бити постављени у ред прво по броју улаза , а затим и лексикографским редом узевши у обзир дати број улаза , који дају обилазак . Експлицитно : ( ) 1 ) 1,1 )2 )1 ) 1,1,1 ) 1,2) 2,1 )3) 1,1 )2 )1 ) итд . Ово може бити тумачено као уношења на мапу бинарног стабла бесконачне дубине на ово стабло и онда примењивање обиласка у ширину . Заменити доње ивице повезивањем родитељског члана на његов следечи а затим дете са десним ивицама првогд детета са другим , другог са трећим и тако дања . Иако сваким корако може ићи или доле или лево , који показује односе између бесконачног бинарног стабла и нумерисања одозго ; сума свих улаза одговара дистанци од корена , који одговара-1 на дубини н-1 у бесконачном бинарном стаблу . Референце Литература Dale , Nell. Lilly , Susan D . " Pascal Plus Data Structures " . D. C. Heath and Company . Lexington , MA. Fourth Edition . Drozdek , Adam . " Data Structures and Algorithms in C++ " . Brook / Cole . Pacific Grove , CA . Second edition. http://www.math.northwestern.edu/ ~mlerma / courses / cs310-05s / notes / dm-treetran Спољашње везе 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 # . See tree traversal implemented in various programming language on Rosetta Code Tree traversal without recursion Стабла ( структуре података ) Алгоритми Рекурзије