C Academy · Lekcja

Przechodzenie drzewa

In-order, pre-order i post-order.

Przechodzenie drzewa to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Czym jest przechodzenie drzewa

Przechodzenie drzewa to systematyczny sposób odwiedzenia każdego węzła drzewa dokładnie raz.

Trzy klasyczne porządki przeszukiwania w głąb to in-order, pre-order i post-order. Różnią się tylko tym, kiedy przetwarzany jest bieżący węzeł względem jego poddrzew.

Przechodzenie in-order

Przechodzenie in-order odwiedza lewe poddrzewo, następnie węzeł, a na końcu prawe poddrzewo.

W przypadku BST wypisuje wartości w rosnącej kolejności, dzięki czemu jest najbardziej użytecznym sposobem przechodzenia dla drzew wyszukiwania.

void in_order(Node *root) {
    if (root == NULL) return;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
}

Przechodzenie pre-order

Przechodzenie pre-order najpierw odwiedza węzeł, następnie lewe poddrzewo, a na końcu prawe poddrzewo.

Jest przydatne do kopiowania drzewa lub tworzenia wyrażenia w notacji prefiksowej, ponieważ korzeń jest wypisywany przed jego dziećmi.

void pre_order(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    pre_order(root->left);
    pre_order(root->right);
}

Przechodzenie post-order

Przechodzenie post-order najpierw odwiedza oba poddrzewa, a dopiero na końcu sam węzeł.

Ponieważ dzieci są przetwarzane przed rodzicem, ten porządek jest dokładnie tym, czego potrzeba do zwalniania drzewa — węzeł nigdy nie jest używany po usunięciu jego dzieci.

void post_order(Node *root) {
    if (root == NULL) return;
    post_order(root->left);
    post_order(root->right);
    printf("%d ", root->value);
}

Wspólny schemat

Wszystkie trzy sposoby przechodzenia w głąb mają ten sam szkielet: przypadek bazowy NULL, rekurencyjne przejście do lewego dziecka, rekurencyjne przejście do prawego dziecka oraz krok odwiedzenia.

Tylko położenie kroku odwiedzenia decyduje o nazwie danego porządku.

/* visit position decides the order:
 * pre  : VISIT, left, right
 * in   : left, VISIT, right
 * post : left, right, VISIT
 */

In-order wypisuje wartości posortowane

Ten program tworzy małe BST i wykonuje przechodzenie in-order, pokazując właściwość posortowanego wyniku.

Wartości pojawiają się od najmniejszej do największej niezależnie od kolejności wstawiania.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7,12};
    for(int i=0;i<6;i++) root=insert(root,d[i]);
    in_order(root);
    printf("\n");
    return 0;
}

Porównanie trzech porządków

Dla drzewa z korzeniem 10, lewym dzieckiem 5 i prawym dzieckiem 15 wyniki są różne:

Pre-order daje 10 5 15. In-order daje 5 10 15. Post-order daje 5 15 10. Wartości węzłów są takie same — zmienia się tylko moment ich odwiedzenia.

/*        10
 *       /  \
 *      5    15
 * pre : 10 5 15
 * in  : 5 10 15
 * post: 5 15 10
 */

Przechodzenie level-order

Przechodzenie wszerz, czyli level-order, odwiedza węzły poziomami, od góry do dołu. Nie ma ono naturalnie rekurencyjnej postaci — wykorzystuje kolejkę.

Dodajemy korzeń do kolejki, a następnie wielokrotnie pobieramy węzeł, wypisujemy go i dodajemy do kolejki jego dzieci.

void level_order(Node *root) {
    if (!root) return;
    Node *queue[100];
    int head = 0, tail = 0;
    queue[tail++] = root;
    while (head < tail) {
        Node *n = queue[head++];
        printf("%d ", n->value);
        if (n->left)  queue[tail++] = n->left;
        if (n->right) queue[tail++] = n->right;
    }
}

Przechodzenie napędza rzeczywiste operacje

Przechodzenie jest schematem dla każdej operacji, która musi dotknąć każdego węzła, a nie tylko go wypisać.

Zastąpienie kroku odwiedzenia sumowaniem wartości, znajdowaniem maksimum lub kopiowaniem węzłów pozwala wykonać te zadania przy użyciu tej samej struktury.

int sum_tree(Node *root) {
    if (root == NULL) return 0;
    return root->value
         + sum_tree(root->left)
         + sum_tree(root->right);
}

Koszt przechodzenia

Każde przechodzenie odwiedza każdy węzeł raz, więc działa w czasie proporcjonalnym do n, czyli liczby węzłów.

Rekurencja wykorzystuje stos o rozmiarze proporcjonalnym do wysokości drzewa: w przypadku drzewa zrównoważonego jest to log(n), a w najgorszym przypadku n.

Wszystkie trzy naraz

Ten program wypisuje dla tego samego drzewa wyniki pre-order, in-order i post-order, aby można było porównać je obok siebie.

Zwróć uwagę, że na wynikową sekwencję wpływa tylko położenie wywołania wypisywania.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }

int main(void){
    Node *root = cn(10);
    root->left = cn(5); root->right = cn(15);
    pre(root);  printf("\n");
    ino(root);  printf("\n");
    post(root); printf("\n");
    return 0;
}

Szybkie sprawdzenie

Wybierz właściwy sposób przechodzenia do danego zadania.

Podsumowanie

Przechodzenia w głąb mają wspólny rekurencyjny szkielet; położenie kroku odwiedzenia decyduje o tym, czy jest to pre-order, in-order czy post-order. Przechodzenie in-order drzewa BST daje posortowany wynik, a post-order jest bezpiecznym porządkiem zwalniania pamięci.

Przechodzenie level-order odbywa się wszerz i wykorzystuje kolejkę. Każdy z tych sposobów odwiedza każdy węzeł raz, w czasie O(n).

Często zadawane pytania

Czy lekcja „Przechodzenie drzewa” jest bezpłatna?

Tak — pełny tekst „Przechodzenie drzewa” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Przechodzenie drzewa”?

In-order, pre-order i post-order. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Przechodzenie drzewa”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy