Loading AI tools
Z Wikipedii, wolnej encyklopedii
Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa.
Pre-order - jeden ze sposobów przechodzenia drzewa | |
Rodzaj |
przechodzenie |
---|---|
Struktura danych |
drzewo |
Wyróżnia się 3 sposoby rekursywnego przejścia drzewa binarnego:
gdzie: Visit – „odwiedź” węzeł, Left – przejdź lewe poddrzewo, Right – przejdź prawe poddrzewo.
W przypadku gdy dane drzewo jest binarnym drzewem AST przejścia określa się również:
Niniejsze algorytmy rekurencyjne działają na drzewie binarnym:
PRE-ORDER(wierzchołek_v)
{
wypisz wierzchołek_v.wartość
jeżeli wierzchołek_v.lewy_syn != null to PRE-ORDER(wierzchołek_v.lewy_syn)
jeżeli wierzchołek_v.prawy_syn != null to PRE-ORDER(wierzchołek_v.prawy_syn)
}
Działanie jest wykonywane najpierw na rodzicu, następnie na synach.
IN-ORDER(wierzchołek_v)
{
jeżeli wierzchołek_v.lewy_syn != null to IN-ORDER(wierzchołek_v.lewy_syn)
wypisz wierzchołek_v.wartość
jeżeli wierzchołek_v.prawy_syn != null to IN-ORDER(wierzchołek_v.prawy_syn)
}
Najpierw wykonywane jest działanie na jednym z synów, następnie na rodzicu i na końcu na drugim synu. Przechodząc w ten sposób drzewo poszukiwań binarnych, otrzymuje się posortowane wartości wszystkich węzłów. Dzieje się tak dlatego, że w drzewie poszukiwań binarnych wartości lewego syna węzła n oraz wszystkich jego potomków są mniejsze od wartości n, a wartości prawego syna i jego potomków większe od wartości n.
POST-ORDER(wierzchołek_v)
{
jeżeli wierzchołek_v.lewy_syn != null to POST-ORDER(wierzchołek_v.lewy_syn)
jeżeli wierzchołek_v.prawy_syn != null to POST-ORDER(wierzchołek_v.prawy_syn)
wypisz wierzchołek_v.wartość
}
Działanie jest wykonywane najpierw na wszystkich synach, na końcu na rodzicu.
Następujące algorytmy działają na ogólnym drzewie, którego każdy wierzchołek może mieć dowolnie wiele synów:
PRE-ORDER(wierzchołek_v)
{
wypisz wierzchołek_v.wartość
dla każdego wierzchołka w będącego synem wierzchołka_v:
PRE-ORDER(w)
}
POST-ORDER(wierzchołek_v)
{
dla każdego wierzchołka w będącego synem wierzchołka_v:
POST-ORDER(w)
wypisz wierzchołek_v.wartość
}
W tym drzewie binarnym podstawowe algorytmy odwiedzają węzły w następującej kolejności:
(1*(2-3))+(4+5)
Notacja wrostkowa wymaga nawiasów do zdefiniowania kolejności wykonywania operacji.
Część nawiasów z powyższego zapisu może zostać opuszczona bez uszczerbku dla wyniku wyrażenia arytmetycznego. Jednak po usunięciu nadmiarowych (z punktu widzenia poprawności wyniku) nawiasów zapis przestanie być wzajemnie jednoznaczny z przytoczonym drzewem.
Konkretniej: z przytoczonego drzewa wynika, że operacja +(4,5) powinna zostać wykonana przed + z korzenia. Po opuszczeniu nawiasów powstałaby dowolność w kolejności wykonywania + i z zapisu bez 'nadmiarowych' nawiasów byłoby możliwe wyprowadznie więcej niż jednego drzewa. Inaczej: z łączności dodawania wynika, że na drzewie składniowym dopuszczalne są obroty operacji + względem siebie.
+ * 1 - 2 3 + 4 5
lub nawiązując do języków programowania:
plus(razy(1,minus(2,3)),plus(4,5))
1 2 3 - * 4 5 + +
W latach 70. kalkulatory RPN były popularne w kręgach finansowych. Obliczenia z wykorzystaniem RPN używają stosu. Współcześnie powyższe wyrażenie może zostać wykonane przy pomocy kalkulatora dc.
$ dc
1 2 3 - * 4 5 + +
p
8
Komenda p zwraca wartość na wierzchołku stosu, czyli w tym przypadku ostateczny wynik wyrażenia.
Istnieje również metoda przechodzenia levelorder, która polega na odwiedzaniu wierzchołków kolejno według wzrastającego poziomu zagłębienia. Jest ona implementowana przy użyciu algorytmu przeszukiwania wszerz (BFS), np. z wykorzystaniem kolejki. W przykładowym drzewie powyżej metoda ta odwiedza węzły w kolejności:
LEVEL-ORDER(wierzchołek_v)
{
utwórz kolejkę wierzchołków k
wstaw wierzchołek_v do kolejki
dopóki kolejka nie jest pusta:
pobierz z kolejki wierzchołek w
wypisz wierzchołek_w.wartość
dla każdego wierzchołka u będącego potomkiem wierzchołka w:
wstaw wierzchołek u do kolejki
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.