Klasa III - Przechodzenie drzew binarnych

Drzewa odzwierciedlają różnego rodzaju struktury. W węzłach są przechowywane różne informacje. Często będziemy spotykać się z zadaniem, które wymaga odwiedzenia każdego węzła drzewa i przetworzenia informacji przechowywanych w węźle. Zadanie to realizują algorytmy przechodzenia drzewa (ang. tree traversal algorithm). Polegają one na poruszaniu się po drzewie od węzła do węzła wzdłuż krawędzi w pewnym porządku i przetwarzaniu danych przechowywanych w węzłach. Istnieje kilka takich algorytmów o różnych własnościach. Omówimy je w tym rozdziale.

Algorytm DFS

Odwiedzenie węzła (ang. node visit) polega na dojściu do danego węzła po strukturze drzewa oraz przetworzenie danych zawartych w węźle. Przeszukiwanie w głąb (ang. Depth First Search - DFS) jest bardzo popularnym algorytmem przechodzenia przez wszystkie węzły poddrzewa, którego korzeniem jest węzeł startowy (jeśli węzłem startowym będzie korzeń drzewa, to DFS przejdzie przez wszystkie węzły zawarte w drzewie). Zasada działania tego algorytmu opiera się na rekurencji lub stosie, którym zastępujemy wywołania rekurencyjne. Ze względu na kolejność odwiedzin węzłów wyróżniamy trzy odmiany DFS (istnieją jeszcze trzy dalsze będące "lustrzanymi odbiciami"):

DFS: pre-order – przejście wzdłużne

W przejściu wzdłużnym (ang. pre-order traversal) najpierw odwiedzamy korzeń poddrzewa, a następnie przechodzimy kolejno lewe i prawe poddrzewo. Prześledź poniższy przykład:

Stan przejścia	Przetworzone węzły	Opis
	A	Odwiedzamy korzeń A i przechodzimy do lewego syna B, który jest korzeniem lewego poddrzewa dla węzła A.
	A B	Odwiedzamy korzeń B poddrzewa i przechodzimy do lewego syna D, który jest korzeniem poddrzewa dla węzła B.
	A B D	Odwiedzamy D i przechodzimy do H.
	A B D H	Odwiedzamy H. Węzeł nie ma dzieci, zatem lewe poddrzewo dla węzła D (ojca H) zostało przebyte. Wracamy do węzła D i przechodzimy do I, który jest korzeniem prawego poddrzewa dla węzła D.
	A B D H I	Odwiedzamy I. Węzeł jest liściem, zatem prawe drzewo węzła D zostało przebyte. Jednocześnie zostało przebyte całe lewe poddrzewo węzła B. Wracamy do B i przechodzimy do E, które jest korzeniem prawego poddrzewa węzła B.
	A B D H I E	Odwiedzamy węzeł E i przechodzimy do lewego poddrzewa, czyli do węzła J.
	A B D H I E J	Wracamy do korzenia A, ponieważ całe lewe poddrzewo zostało przebyte. Teraz w analogiczny sposób odwiedzamy prawe poddrzewo, rozpoczynając od jego korzenia C.
	A B D H I E J C	Odwiedzamy C i przechodzimy do lewego poddrzewa.
	A B D H I E J C F	Odwiedzamy F i przechodzimy do lewego poddrzewa.
	A B D H I E J C F K	Odwiedzamy K i wracamy do C (lewe poddrzewo węzła C jest przebyte), a następnie przechodzimy do prawego poddrzewa.
	A B D H I E J C F K G	Odwiedzamy G. Drzewo zostało przebyte.

Na poniższym rysunku zaznaczyliśmy linię przejścia przez kolejne węzły drzewa.

→ pre-order →

Algorytm rekurencyjny DFS:preorder dla drzewa binarnego

Wejście

–

wskazanie węzła startowego drzewa binarnego

Wyjście:

przetworzenie wszystkich węzłów drzewa.

Lista kroków:

K01:	Jeśli v = nil, to zakończ	; koniec rekurencji
K02:	Odwiedź węzeł wskazany przez v
K03:	preorder(v→left)	; przejdź rekurencyjnie przez lewe poddrzewo
K04:	preorder(v→right)	; przejdź rekurencyjnie przez prawe poddrzewo
K05:	Zakończ

DFS: in-order – przejście poprzeczne

W przejściu poprzecznym (ang. in-order traversal) najpierw przechodzimy lewe poddrzewo danego węzła, następnie odwiedzamy węzeł i na koniec przechodzimy prawe poddrzewo.

Stan przejścia	Przetworzone węzły	Opis
	H	Rozpoczynamy w korzeniu A. Jednakże węzła A nie przetwarzamy, lecz przechodzimy do lewego syna B. Tutaj dalej przechodzimy do D i H. Węzeł H nie ma dzieci, więc przechodzenie do lewego poddrzewa się kończy i węzeł H zostaje przetworzony jako pierwszy.
	H D	Lewe poddrzewo węzła D zostało przebyte, zatem przetwarzamy węzeł D i przechodzimy do prawego poddrzewa, którego korzeniem jest węzeł I.
	H D I	Węzeł I jest liściem, zatem nie posiada lewego poddrzewa. Przetwarzamy węzeł I.
	H D I B	Lewe poddrzewo węzła B zostało przebyte. Przetwarzamy węzeł B i przechodzimy do jego prawego poddrzewa rozpoczynającego się w węźle E.
	H D I B J	Będąc w węźle E najpierw przechodzimy jego lewe poddrzewo, czyli idziemy do węzła J. Węzeł J jest liściem i nie posiada dalszych poddrzew. Przetwarzamy J i wracamy do E.
	H D I B J E	Lewe poddrzewo węzła E zostało przebyte. Przetwarzamy węzeł E. Ponieważ nie posiada on prawego poddrzewa, wracamy do A.
	H D I B J E A	Lewe poddrzewo węzła A zostało przebyte. Przetwarzamy A i przechodzimy do prawego poddrzewa rozpoczynającego się od węzła C.
	H D I B J E A K	Będąc w węźle C przechodzimy do lewego poddrzewa rozpoczynającego się od węzła F, a tam dalej przechodzimy do następnego lewego poddrzewa, czyli do węzła K. Ten węzeł jest liściem i nie posiada dalszych poddrzew. Przetwarzamy K i wracamy do F.
	H D I B J E A K F	Lewe poddrzewo węzła F zostało przebyte. Przetwarzamy F. Ponieważ brak prawego poddrzewa, wracamy do C.
	H D I B J E A K F C	Lewe poddrzewo węzła C zostało przebyte, przetwarzamy C i przechodzimy do prawego poddrzewa, czyli do węzła G.
	H D I B J E A K F C G	G jest liściem, przetwarzamy G i kończymy.

DFS: post-order – przejście wsteczne

W przejściu wstecznym (ang. post-order traversal) najpierw przechodzimy lewe poddrzewo, następnie prawe, a dopiero na końcu przetwarzamy węzeł.

Stan przejścia	Przetworzone węzły	Opis
	H	Rozpoczynamy w korzeniu A. Najpierw przechodzimy lewe poddrzewo. Idziemy do B. Tutaj również przechodzimy lewe poddrzewo i idziemy do D, a następnie do H. Węzeł H jest liściem i nie posiada poddrzew. Przetwarzamy H i wracamy do D.
	H I	Lewe poddrzewo węzła D jest przebyte, przechodzimy poddrzewo prawe. Idziemy do węzła I. Ponieważ jest on liściem, to nie posiada poddrzew. Przetwarzamy I. Wracamy do D.
	H I D	Oba poddrzewa węzła D zostały przebyte, przetwarzamy D i wracamy do B.
	H I D J	Dla węzła B przebyte zostało poddrzewo lewe. Teraz przechodzimy przez jego prawe poddrzewo. Idziemy do E i do J (lewe poddrzewo E). J jest liściem i nie posiada dalszych poddrzew, zatem przetwarzamy J i wracamy do E.
	H I D J E	Lewe poddrzewo węzła E zostało przebyte. Nie ma prawego poddrzewa dla E, zatem przetwarzamy E i wracamy do B.
	H I D J E B	Lewe i prawe poddrzewo węzła B jest przebyte. Przetwarzamy węzeł B i wracamy do A.
	H I D J E B K	Lewe poddrzewo węzła A zostało przebyte. Przechodzimy do prawego poddrzewa, czyli do węzła C, następnie do F (lewe poddrzewo C) i do K (lewe poddrzewo F). K jest liściem i nie posiada poddrzew. Przetwarzamy K i wracamy do F.
	H I D J E B K F	Lewe poddrzewo węzła F jest przebyte, a prawego poddrzewa brak. Przetwarzamy F i wracamy do C.
	H I D J E B K F G	Lewe poddrzewo węzła C jest przebyte, przechodzimy do poddrzewa prawego, czyli do węzła G. Węzeł G jest liściem i nie posiada poddrzew. Przetwarzamy G i wracamy do C.
	H I D J E B K F G C	Oba poddrzewa węzła C zostały przebyte. Przetwarzamy C i wracamy do A.
	H I D J E B K F G C A	Oba poddrzewa węzła A zostały przebyte. Przetwarzamy A i kończymy

→ post-order →

Algorytm rekurencyjny DFS:postorder dla drzewa binarnego