Metoda preorder Dane wejściowe L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka v - numer węzła wejściowego Lista kroków preorder(v) K01: Przetwórz węzeł v K02: Jeśli L[v].left > 0, wywołaj rekurencyjnie preorder(L[v].left) K03: Jeśli L[v].right > 0, wywołaj rekurencyjnie preorder(L[v].right) K04: Zakończ	Metoda inorder Dane wejściowe L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka v - numer węzła wejściowego Lista kroków inorder(v) K01: Jeśli L[v].left > 0, wywołaj rekurencyjnie inorder(L[v].left) K02: Przetwórz węzeł v K03: Jeśli L[v].right > 0, wywołaj rekurencyjnie inorder(L[v].right) K04: Zakończ
Metoda postorder Dane wejściowe L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka v - numer węzła wejściowego Lista kroków postorder(v) K01: Jeśli L[v].left > 0, wywołaj rekurencyjnie postorder(L[v].left) K02: Jeśli L[v].right > 0, wywołaj rekurencyjnie postorder(L[v].right) K03: Przetwórz węzeł v K04: Zakończ	BFS W odróżnieniu od ww. metod metoda BFS przechodzi przez kolejne węzły na poszczególnych poziomach drzewa binarnego. Do tego celu wymagana jest dodatkowa struktura danych - kolejka, która zapamiętuje numery wierzchołków do odwiedzenia. Kolejka musi obsługiwać następujące funkcje: clear() - czyści kolejkę z ewentualnych danych empty() - zwraca true, jeśli kolejka nie zawiera danych push(v) - wprowadza wierzchołek v na koniec kolejki pop() - pobiera i zwraca numer wierzchołka z początku kolejki Kolejkę możemy zrealizować w postaci listy jednokierunkowej: dopisujemy do końca listy (musimy zatem pamiętać adres ostatniego elementu, aby nie przechodzić listy od początku), a pobieramy z początku listy. Możemy również skorzystać z biblioteki STL, gdzie znajduje się szablon kontenera <queue>. Jednakże w obu przypadkach będą do rozwiązania dość czasochłonne. My posiadamy dużo prostszy i szybszy sposób. Jeśli znamy ilość wszystkich wierzchołków w drzewie (a tak zwykle przecież jest), to maksymalna długość kolejki wyniesie: Algortmy obsługi kolejki dla metody BFS Dane wejściowe Q[ ]: - tablica, w której realizujemy kolejkę nQ - długość tablicy Q[ ] bQ - wskazuje element na początku kolejki - zawiera jego indeks eQ - wskazuje element tuż za końcem kolejki - zawiera jego indeks Listy kroków clear() K01: bQ ← 0; eQ ← 0 K02: Zakończ empty() K01: Jeśli bQ = eQ, zwróć true. Inaczej zwróć false K02: Zakończ push(v) K01: Q[eQ] ← v K02: eQ ← (eQ + 1) modulo nQ K03: Zakończ pop() K01: v ← Q[bQ] K02: bQ ← (bQ + 1) modulo nQ K03: Zwróć v i zakończ Algorytm BFS Dane wejściowe n - ilość wierzchołków w drzewie binarnym L[ ] - tablica list sąsiedztwa vr - numer wierzchołka będącego korzeniem drzewa (lub numer wierzchołka, od którego chcemy rozpocząć przetwarzanie drzewa binarnego). Lista kroków K01: Twórz kolejkę o rozmiarze K02: clear() K03: push(vr) K04: Dopóki empty() = false: wykonuj kroki K05...K08 K05: v ← pop() K06: Przetwórz węzeł v K07: Jeśli L[v].left > 0, push(L[v].left) K08: Jeśli L[v].right > 0, push(L[v].right) K09: Zakończ
inorder : < 4 2 8 5 9 1 6 3 10 7 11 > preorder : < 1 2 4 5 8 9 3 6 7 10 11 > postorder : < 4 8 9 5 2 6 10 11 7 3 1 >
Rekurencyjne wyszukiwanie w drzewach BST. SEARCH_BST (x,v) // v-wyszukiwana wartość // x wskaźnik do korzenia drzewa { JEśELI ((x=nil) ∪ (v=x.key) { ZWROC (x); } JEśELI (v < x.key) { ZWROC (SEARCH_BST (x.left,v)); } WPP { ZWROC (SEARCH_BST (x.right, v)); } }
Wyszukiwanie w drzewie AVL: SEARCH_AVL (x,v) // v-wyszukiwana wartość // x wskaźnik do korzenia drzewa { DOPOKI (x≠nil) ∩ (v ≠x.key) { JEśELI (v < x.key) { x:= x.left; } WPP { x:= x. right; { ZWROC (x); }

---