Podręcznik

Wyróżniamy trzy podstawowe sposoby poruszania się po BST (w tzw. przechodzeniu w głąb, ang. depth-first traversal):

• w kolejności inorder: najpierw lewe poddrzewo, potem węzeł, a następnie prawe poddrzewo,
  
• w kolejności preorder: najpierw węzeł, potem lewe poddrzewo, a następnie prawe poddrzewo,
  
• w kolejności postorder: najpierw lewe poddrzewo, potem prawe poddrzewo, a na samy końcu węzeł.
  

Węzeł drzewa może opisać za pomocą struktury zawierającej dwa wskaźniki na dzieci danego węzła.

struct Node {
    int key;
    Node* left;
    Node* right;
};

Jedną z najczęściej stosowanych metod jest przechodzenie typu inorder, które odwiedza najpierw lewe poddrzewo, następnie przetwarza bieżący węzeł, a na końcu przechodzi do prawego poddrzewa. W przypadku drzewa BST ta metoda zwraca elementy w kolejności rosnącej, co czyni ją idealną do uporządkowanego wypisywania danych. Jest to jedna z metod sortowania liczb przy wykorzystaniu drzewa BST. Poniżej przedstawiono prosty kod funkcji, która umożliwia przejście po drzewie w kolejności inorder.
 

void inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

Inną metodą jest preorder, gdzie najpierw przetwarzany jest bieżący węzeł, następnie przechodzi się do lewego poddrzewa, a na końcu do prawego. Taki sposób przechodzenia sprawdza się dobrze przy zapisywaniu struktury drzewa do pliku lub przy klonowaniu drzewa, ponieważ zachowuje hierarchię węzłów. Poniżej przedstawiono kod aplikacji realizujący przejście preorder po drzewie BST.

void preorder(Node* root) {
    if (root != nullptr) {
        cout << root->key << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

Postorder to metoda, w której najpierw przetwarzane są oba poddrzewa najpierw lewe, potem prawe, a dopiero na końcu sam węzeł. Jest szczególnie przydatna wtedy, gdy musimy usunąć całe drzewo, ponieważ pozwala najpierw pozbyć się potomków, zanim usuniemy ich rodziców. Poniżej przedstawiono kod funkcji do przechodzenia po drzewie w kolejności postorder.

void postorder(Node* root) {
    if (root != nullptr) {
        postorder(root->left);
        postorder(root->right);
        cout << root->key << " ";
    }
}