Procházení stromů

Na rozdíl od spojových seznamů, jednorozměrných polí a dalších lineárních datových struktur, které jsou kanonicky procházeny v lineárním pořadí, lze stromy procházet více způsoby. Mohou být procházeny v pořadí hloubka-první nebo šířka-první. Existují tři běžné způsoby procházení v pořadí do hloubky: in-order, pre-order a post-order. Kromě těchto základních způsobů procházení jsou možná různá složitější nebo hybridní schémata, například prohledávání s omezením hloubky, jako je iterativní prohledávání s prohloubením do hloubky. Ten, stejně jako prohledávání do šířky, lze použít i k procházení nekonečných stromů, viz níže.

Datové struktury pro procházení stromůUpravit

Procházení stromu zahrnuje iteraci nad všemi uzly určitým způsobem. Protože z daného uzlu existuje více než jeden možný další uzel (nejedná se o lineární datovou strukturu), pak za předpokladu sekvenčního výpočtu (nikoli paralelního) musí být některé uzly nějakým způsobem odloženy – uloženy pro pozdější návštěvu. To se často provádí pomocí zásobníku (LIFO) nebo fronty (FIFO). Protože strom je autoreferenční (rekurzivně definovaná) datová struktura, lze velmi přirozeným a jasným způsobem definovat procházení pomocí rekurze nebo, jemněji řečeno, korkurze; v těchto případech jsou odložené uzly implicitně uloženy v zásobníku volání.

Prohledávání do hloubky je snadno realizovatelné pomocí zásobníku, včetně rekurzivního (pomocí zásobníku volání), zatímco prohledávání do šířky je snadno realizovatelné pomocí fronty, včetně korkurzivního.:45-61

Hloubkové prohledávání binárního stromuEdit

Hloubkové procházení (tečkovaná cesta) binárního stromu:

• Předřazení (přístup k uzlu na červené pozici ●):

  F, B, A, D, C, E, G, I, H;

• In-order (přístup k uzlu na pozici zelené ●):

  A, B, C, D, E, F, G, H, I;

• Post-order (přístup k uzlu na pozici modré ●):

  A, C, E, D, B, H, I, G, F.

Tyto prohledávání se označují jako prohledávání do hloubky (DFS), protože prohledávací strom je na každém potomkovi prohlouben co nejvíce, než se přejde k dalšímu sourozenci. Pro binární strom jsou definovány jako přístupové operace v každém uzlu, počínaje aktuálním uzlem, jejichž algoritmus je následující:

Obecný rekurzivní vzor procházení binárního stromu je následující:

1. Přejděte o jednu úroveň níže na rekurzivní argument N. Pokud N existuje (není prázdné), proveďte následující tři operace v určitém pořadí: L: Rekurzivně projděte levý podstrom N. R: Rekurzivně projděte pravý podstrom N. N: Přístup k aktuálnímu uzlu N (návštěva).
2. Vrátí se tak, že vystoupá o úroveň výš a dorazí k nadřazenému uzlu N.

Existují tři způsoby (vzory), na které pozici parkuru (traverzování) vzhledem k uzlu (na obrázku: červená, zelená nebo modrá) se má uskutečnit návštěva (přístup) uzlu. Volba přesně jedné barvy určuje přesně jednu návštěvu uzlu, jak je popsáno níže. Přístup při všech třech barvách vede k trojí návštěvě téhož uzlu, čímž se získá sekvencování „all-order“:

F-B-A-A-A-B-D-C-C-C-D-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F

Pre-order, NLREdit

1. Přístup k datové části aktuálního uzlu (na obrázku: pozice červená).
2. Projdi levý podstrom rekurzivním voláním funkce pre-order.
3. Projdi pravý podstrom rekurzivním voláním funkce pre-order.

Procházka s předřazením je topologicky setříděná, protože nadřazený uzel je zpracován dříve než některý z jeho podřízených uzlů.

In-order, LNREdit

1. Prochází levý podstrom rekurzivním voláním funkce in-order.
2. Přistup k datové části aktuálního uzlu (na obrázku: pozice zelená).
3. Projdi pravý podstrom rekurzivním voláním funkce in-order.

V binárním vyhledávacím stromu uspořádaném tak, že v každém uzlu je klíč větší než všechny klíče v jeho levém podstromu a menší než všechny klíče v jeho pravém podstromu, získává procházení in-order klíče ve vzestupném seřazení.

Reverse in-order, RNLEdit

1. Prochází pravý podstrom rekurzivním voláním funkce reverse in-order.
2. Prochází datovou část aktuálního uzlu.
3. Prochází levý podstrom rekurzivním voláním funkce reverse in-order.

V binárním vyhledávacím stromu se při reverzním procházení in-order získávají klíče v sestupně seřazeném pořadí.

Post-order, LRNEdit

1. Prochází levý podstrom rekurzivním voláním funkce post-order.
2. Projdi pravý podstrom rekurzivním voláním funkce post-order.
3. Přístup k datové části aktuálního uzlu (na obrázku: pozice modrá).

Sledování procházení se nazývá sekvencování stromu. Stopa procházení je seznam jednotlivých navštívených uzlů. Žádná sekvencializace podle pre-, in- nebo post-pořadí nepopisuje základní strom jednoznačně. Při daném stromu s různými prvky stačí k jednoznačnému popisu stromu buď pre-order, nebo post-order ve spojení s in-order. Avšak pre-order s post-order zanechává ve struktuře stromu určitou nejednoznačnost.

Generic treeEdit

Pro procházení libovolného stromu s hloubkovým vyhledáváním proveďte v každém uzlu následující operace:

1. Pokud uzel není přítomen, vraťte.
2. Přistupte (= navštivte) uzel (pozice před pořadím).
3. Pro každé i od 1 do number_of_children – 1 proveďte:
   1. Rekurzivně projděte i-tého potomka.
   2. Přejdi uzel (pozice v pořadí).
4. Rekurzivně projdi poslední dítě.
5. Přejdi uzel (pozice po pořadí).

V závislosti na daném problému mohou být operace pre-order, post-order a zejména jedna z operací (počet_dětí – 1) in-order prázdné, nebo je požadován přístup pouze ke konkrétnímu dítěti, takže tyto operace jsou nepovinné. V praxi také může být požadována více než jedna operace pre-order, in-order a post-order. Například při vkládání do ternárního stromu se porovnáním položek provede operace pre-order. Následně může být zapotřebí operace post-order pro opětovné vyvážení stromu.

Breadth-first search, nebo level orderEdit

Level-order: F, B, G, A, D, I, C, E, H.

Stromy lze také procházet v pořadí úrovní, kdy před přechodem na nižší úroveň navštívíme každý uzel na dané úrovni. Toto prohledávání se označuje jako prohledávání podle šířky (breadth-first search, BFS), protože před přechodem do další hloubky se prohledávaný strom na každé hloubce co nejvíce rozšíří.

Jiné typyUpravit

Existují také algoritmy procházení stromů, které se neřadí ani mezi prohledávání podle hloubky, ani mezi prohledávání podle šířky. Jedním z takových algoritmů je prohledávání stromu Monte Carlo, které se soustředí na analýzu nejslibnějších tahů a rozšiřování prohledávacího stromu zakládá na náhodném výběru vzorku prohledávaného prostoru.