Úvod

Prechod stromom (tree traversal) je proces, pri ktorom sa systematickým spôsobom navštívi každý vrchol stromu práve raz. Je to bežný proces, ak sa má na každom prvku stromu vykonať nejaká operácia. Na túto sa dá pozerať ako na jednoduchý sekvenčný proces - jednotlivé vrcholy navštevujú v určitom poradí. Podľa toho sú rozdelené metódy prechádzania do skupín.

Rozlišujú sa tri základné usporiadania, ktoré sú prirodzeným dôsledkom stromovej štruktúry. Tak ako samotná štruktúra sa dajú vhodne rekurzívne vyjadriť.
Popísané algoritmy sú riešené pre binárne stromy, ale dajú sa zovšeobecniť aj pre ostatné stromové štruktúry.
Označme v binárnom strome koreň K, jeho ľavého syna L a pravého syna R.

^ TOP

Preorder

Preorder tree walk vypíše hodnotu koreňa pre hodnotami v oboch podstromoch, teda v poradí K, L, R.

Prechod stromu pomocou preorderu a zároveň vkladanie hodnôt do nového stromu je častá technika na vytvorenie úplnej kópie binárneho stromu. Preorder sa tiež používa na vyhodnotenie výrazu uloženého v strome. Prechádza sa výrazom zprava doľava a ukladajú sa elementy do zásobníka.

    preorder(node)
      print node.value
      if node.left  != null then preorder(node.left)
      if node.right != null then preorder(node.right)      
      

^ TOP

Inorder

Inorder tree walk vypíše hodnotu koreňa medzi hodnotami v ľavom a pravom podstrome, teda v poradí L, K, R..

Táto medóda prechodu stromom prechádza hodnoty v stúpajúcom poradí. To je preto, lebo z definície je každý prvok v ľavom podstrome menší ako v koreni a v pravom podstrome väčší ako v koreni. Podobne, prechod stromom metódou reverzného inorderu dáva hodnoty utriedené zostupne.

    inorder(node)
      if node.left  != null then inorder(node.left)
      print node.value
      if node.right != null then inorder(node.right)     
      

^ TOP

Postorder

Postorder tree walk vypíše najprv hodnoty v podstromoch a až potom hodnotu koreňa, teda v poradí L, R, K.

Táto metóda sa tiež volá prehľadávanie do hĺbky. Tak ako je preorder vhodne spojený so zásobníkom, tak je postorder spojený s frontom. Hodnoty sa vypíšu v poradí závisiacom od svojej vzdialenosti od koreňa.

    postorder(node)
      if node.left  != null then  postorder(node.left)
      if node.right != null then postorder(node.right)
      print node.value     
      

^ TOP

Level-order

Level-order tree walk prechádza najprv všetky vrcholy na tej istej úrovni, až potom ide o úroveň nižšie. Takýto prechod sa tiež volá prehľadávanie do šírky. Príklad uvedený v kóde používa zásobník a potrebuje v najhoršom prípade pamäť veľkosť ktorej sa rovná počtu vrcholov na danej úrovni (maximálne n/2, kde n je celkový počet vrcholov).

    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)   
      

^ TOP