Procházení stromu

Procházení stromu (také prohledávání stromu) je úloha z oblasti algoritmů, jejíž podstatou je postupné „navštívení“ všech položek datového stromu. Protože na tento strom může být nahlíženo jako na graf, jedná se zároveň o úlohu z teorie grafů.

Různé přístupy k procházení stromu jsou obvykle ilustrovány na binárních stromech, neboť rozšíření na další stromy bývá poměrně přímočaré.

Dva základní přístupy k procházení stromu jsou prohledávání do hloubky a prohledávání do šířky, přičemž oba mají různé podvarianty (zleva, zprava, …). Kromě pořadí, v kterém jsou vrcholy navštíveny, se také liší použitím různých pomocných datových struktur. Prohledávání do hloubky je přirozeně rekurzivní proces, při kterém je přirozené použití zásobníku, ať už definovaném v programu explicitně, nebo implicitním využitím zásobníku volání. Naopak při prohledávání do šířky je typicky využívána fronta.

Pokud není cílem projít celý strom, ale jen najít určitou hodnotu, může být strom předem sestaven speciálním způsobem jako vyhledávací strom (nejčastěji binární vyhledávácí strom) – v něm se pak jako efektivní uplatňují speciální varianty algoritmů. Jiné speciální varianty algoritmů se uplatňují při prohledávání stavového prostoru (stavový prostor mívá rovněž charakter stromu). V oblasti umělé inteligence v počítačových hrách jsou úspěšné heuristické algoritmy, například prohledávání stromu metodou Monte Carlo odvozené od obecné myšlenky metody Monte Carlo.

Reference

V tomto článku byl použit překlad textu z článku Tree traversal na anglické Wikipedii.