W przeciwieństwie do list połączonych, tablic jednowymiarowych i innych liniowych struktur danych, które są kanonicznie przemierzane w porządku liniowym, drzewa mogą być przemierzane na wiele sposobów. Mogą one być przemierzane w kolejności depth-first lub breadth-first. Istnieją trzy typowe sposoby trawersowania ich w kolejności depth-first: in-order, pre-order i post-order. Poza tymi podstawowymi sposobami, możliwe są różne bardziej złożone lub hybrydowe schematy, takie jak wyszukiwanie z ograniczeniem głębokości, np. iteracyjne pogłębianie wyszukiwania w kolejności pierwszej. To ostatnie, jak również breadth-first search, może być również użyte do trawersowania nieskończonych drzew, patrz poniżej.
Struktury danych dla trawersowania drzewEdit
Trawersowanie drzewa polega na iterowaniu nad wszystkimi węzłami w jakiś sposób. Ponieważ od danego węzła istnieje więcej niż jeden możliwy następny węzeł (nie jest to liniowa struktura danych), to zakładając sekwencyjne obliczanie (nie równoległe), niektóre węzły muszą być w jakiś sposób odroczone – przechowywane do późniejszego odwiedzenia. Często odbywa się to za pomocą stosu (LIFO) lub kolejki (FIFO). Ponieważ drzewo jest samoreferencyjną (rekurencyjnie zdefiniowaną) strukturą danych, traversal może być zdefiniowany przez rekurencję lub, bardziej subtelnie, corecursion, w bardzo naturalny i jasny sposób; w tych przypadkach odroczone węzły są przechowywane niejawnie w stosie wywołań.
Depth-first search jest łatwo zaimplementowany przez stos, w tym rekurencyjnie (przez stos wywołań), podczas gdy breadth-first search jest łatwo zaimplementowany przez kolejkę, w tym corecursively.:45-61
Depth-first search of binary treeEdit
- Pre-order (dostęp do węzła na pozycji czerwonej ●):
F, B, A, D, C, E, G, I, H;
- In-order (dostęp do węzła na pozycji green ●):
A, B, C, D, E, F, G, H, I;
- Post-order (dostęp do węzła na pozycji blue ●):
A, C, E, D, B, H, I, G, F.
Szukania te określane są jako depth-first search (DFS), ponieważ drzewo przeszukiwania jest maksymalnie pogłębiane na każdym dziecku przed przejściem do następnego rodzeństwa. Dla drzewa binarnego są one zdefiniowane jako operacje dostępu w każdym węźle, począwszy od bieżącego węzła, którego algorytm jest następujący:
Ogólny wzorzec rekursywny dla trawersowania drzewa binarnego jest następujący:
- Zejdź o jeden poziom w dół do argumentu rekursywnego N. Jeśli N istnieje (jest niepusty) wykonaj następujące trzy operacje w określonej kolejności: L: Rekursywnie przemierz lewe poddrzewo N. R: Rekursywnie przemierz prawe poddrzewo N. N: Uzyskaj dostęp (odwiedź) sam bieżący węzeł N.
- Powrót przez przejście o jeden poziom wyżej i dotarcie do węzła nadrzędnego węzła N.
Istnieją trzy metody (wzorce), w której pozycji parcours (traversal) względem węzła (na rysunku: czerwonego, zielonego lub niebieskiego) powinna nastąpić wizyta (dostęp) do węzła. Wybór dokładnie jednego koloru determinuje dokładnie jedną wizytę w węźle, zgodnie z opisem poniżej. Dostęp we wszystkich trzech kolorach powoduje trzykrotne odwiedzenie tego samego węzła, co daje sekwencjonowanie „all-order”:
F-B-A-A-B-D-C-C-D-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
Pre-order, NLREdit
- Dostęp do części danych bieżącego węzła (na rysunku: pozycja czerwona).
- Przekraczaj lewe poddrzewo przez rekurencyjne wywołanie funkcji preorder.
- Przekraczaj prawe poddrzewo przez rekurencyjne wywołanie funkcji preorder.
Przedzielenie jest topologicznie posortowane, ponieważ węzeł nadrzędny jest przetwarzany przed wykonaniem któregokolwiek z jego węzłów podrzędnych.
In-order, LNREdit
- Przejrzyj lewy poddrzewo przez rekursywne wywołanie funkcji in-order.
- Dostęp do części danych bieżącego węzła (na rysunku: pozycja zielona).
- Przejście przez prawe poddrzewo przez rekursywne wywołanie funkcji in-order.
W binarnym drzewie wyszukiwania uporządkowanym tak, że w każdym węźle klucz jest większy niż wszystkie klucze w jego lewym poddrzewie i mniejszy niż wszystkie klucze w jego prawym poddrzewie, in-order traversal pobiera klucze w rosnącej posortowanej kolejności.
Odwrócone in-order, RNLEdit
- Przekroczenie prawego poddrzewa przez rekursywne wywołanie funkcji odwróconego in-order.
- Dostęp do części danych bieżącego węzła.
- Przekroczenie lewego poddrzewa przez rekursywne wywołanie funkcji odwróconego in-order.
W drzewie wyszukiwania binarnego, traversal reverse in-order pobiera klucze w porządku sortowanym malejącym.
Post-order, LRNEdit
- Traverse the left subtree by recursively calling the post-order function.
- Przekraczamy prawy poddrzewo przez rekurencyjne wywołanie funkcji post-order.
- Dostęp do części danych bieżącego węzła (na rysunku: pozycja niebieska).
Ślad trawersowania nazywamy sekwencjonowaniem drzewa. Ślad trawersu jest listą każdego odwiedzonego węzła. Żadna sekwencjonowanie zgodnie z pre-, in- lub post-order nie opisuje jednoznacznie drzewa bazowego. Biorąc pod uwagę drzewo z różnymi elementami, albo pre-order albo post-order sparowane z in-order jest wystarczające, aby opisać drzewo jednoznacznie. Jednak pre-order z post-order pozostawia pewną niejednoznaczność w strukturze drzewa.
Generic treeEdit
Aby przemierzyć dowolne drzewo za pomocą wyszukiwania w głąb, wykonaj następujące operacje na każdym węźle:
- Jeśli węzeł nie jest obecny, zwróć.
- Access (= visit) node (pre-order position).
- For each i from 1 to number_of_children – 1 do:
- Recursively traverse i-th child.
- Węzeł dostępu (pozycja in-order).
- Recursywnie przemierzaj ostatnie dziecko.
- Węzeł dostępu (pozycja post-order).
Zależnie od rozpatrywanego problemu, operacje pre-order, post-order, a zwłaszcza jedna z (number_of_children – 1) in-order mogą być nieważne lub wymagany jest dostęp tylko do konkretnego dziecka, więc te operacje są opcjonalne. Również w praktyce może być wymagana więcej niż jedna z operacji pre-order, in-order i post-order. Na przykład, podczas wstawiania do drzewa trójdzielnego, operacja pre-order jest wykonywana poprzez porównywanie elementów. Później może być potrzebna operacja post-order, aby ponownie zbalansować drzewo.
Breadth-first search, czyli kolejność poziomówEdit
Drzewa mogą być również przemierzane w level-order, gdzie odwiedzamy każdy węzeł na poziomie przed przejściem do niższego poziomu. Takie wyszukiwanie jest określane jako breadth-first search (BFS), ponieważ drzewo wyszukiwania jest poszerzane tak bardzo, jak to możliwe na każdej głębokości przed przejściem do następnej głębokości.
Inne typyEdit
Istnieją również algorytmy przeszukiwania drzew, które nie są klasyfikowane ani jako depth-first search, ani breadth-first search. Jednym z takich algorytmów jest przeszukiwanie drzewa Monte Carlo, które koncentruje się na analizie najbardziej obiecujących ruchów, opierając ekspansję drzewa wyszukiwania na losowym próbkowaniu przestrzeni wyszukiwania.
.