0Pricing
C Academy · Lekcja

Węzły i struktura drzewa

Zam modeluje Pan/Pani węzeł za pomocą wskaźników.

Węzły i struktura drzewa to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 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 drzewo binarne

Drzewo binarne to hierarchiczna struktura, w której każdy węzeł przechowuje wartość i odwołania do najwyżej dwojga dzieci: lewego i prawego.

Węzeł znajdujący się najwyżej to korzeń. Węzły bez dzieci to liście. Taka struktura sprawia, że drzewa binarne świetnie nadają się do szybkiego wyszukiwania, sortowania i przetwarzania rekurencyjnego.

Struktura węzła

W języku C modelujemy węzeł za pomocą struktury, która przechowuje dane oraz dwa wskaźniki odnoszące się do tego samego typu.

Każdy wskaźnik wskazuje inny Node albo ma wartość NULL, gdy po danej stronie nie ma dziecka.

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

Dlaczego wskaźniki do tego samego typu

Węzeł nie może zawierać pełnego innego węzła przez wartość, ponieważ wymagałoby to nieskończenie dużej pamięci. Zamiast tego przechowuje wskaźniki do swoich dzieci.

Wskaźniki mają stały rozmiar, więc struktura zachowuje znany rozmiar, a jednocześnie może łączyć się z innymi węzłami na stercie.

struct Node {
    int value;
    struct Node *left;   /* 8 bytes on 64-bit */
    struct Node *right;  /* 8 bytes on 64-bit */
};

typedef dla wygody

Wpisywanie w każdym miejscu struct Node jest uciążliwe. typedef pozwala pisać po prostu Node.

Znacznik jest nadal potrzebny wewnątrz struktury, ponieważ w tym miejscu typ nie został jeszcze w pełni zdefiniowany.

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Alokowanie węzła

Węzły znajdują się na stercie i są tworzone za pomocą malloc. Ustawiamy wartość oraz inicjalizujemy oba wskaźniki dzieci na NULL.

Przed użyciem pamięci zawsze należy sprawdzić, czy malloc nie zwrócił wartości NULL.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return NULL;
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Ręczne budowanie małego drzewa

Aby zrozumieć połączenia, połączmy ręcznie trzy węzły: korzeń z dwojgiem dzieci.

Ten program buduje drzewo i wyświetla wartości, a następnie normalnie należałoby je zwolnić (co omówimy później).

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

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Node *create_node(int v) {
    Node *n = malloc(sizeof(Node));
    n->value = v; n->left = NULL; n->right = NULL;
    return n;
}

int main(void) {
    Node *root = create_node(10);
    root->left = create_node(5);
    root->right = create_node(15);
    printf("%d %d %d\n", root->left->value, root->value, root->right->value);
    return 0;
}

Docieranie do wnuków

Po drzewie poruszamy się, łącząc operator strzałki. root->left->right przechodzi najpierw do lewego dziecka, a następnie do jego prawego dziecka.

Przed podążeniem za wskaźnikiem należy upewnić się, że nie ma on wartości NULL, w przeciwnym razie program ulegnie awarii.

/* root
 *   \
 *    right (15)
 *        \
 *         right->right (20)
 */
if (root->right != NULL && root->right->right != NULL)
    printf("%d\n", root->right->right->value);

Rekurencyjne zliczanie węzłów

Rekurencja naturalnie pasuje do drzew. Aby policzyć węzły, puste poddrzewo uznajemy za zawierające zero węzłów; w przeciwnym razie dodajemy bieżący węzeł oraz oba poddrzewa.

Sprawdzenie NULL jest przypadkiem bazowym, który zatrzymuje rekurencję.

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

Mierzenie wysokości

Wysokość drzewa to najdłuższa ścieżka od korzenia do liścia, mierzona liczbą krawędzi.

Wybieramy większą z wysokości obu poddrzew i dodajemy jeden. Pustemu drzewu przypisujemy wysokość -1, dzięki czemu pojedynczy węzeł ma wysokość 0.

int height(Node *root) {
    if (root == NULL) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

Rozpoznawanie liści

Liść to węzeł bez dzieci: zarówno left, jak i right mają wartość NULL.

Ta niewielka funkcja pomocnicza jest przydatna w wielu procedurach przechodzenia drzewa i zliczania.

int is_leaf(Node *n) {
    return n != NULL && n->left == NULL && n->right == NULL;
}

Wykorzystanie struktury

W tym przykładzie budujemy małe drzewo i za pomocą funkcji rekurencyjnych wyświetlamy liczbę jego węzłów oraz wysokość.

Proszę zauważyć, że funkcje pomocnicze nie zakładają określonego kształtu drzewa; działają dla każdego drzewa, ponieważ rekurencja podąża za rzeczywistymi wskaźnikami.

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

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }

int main(void){
    Node *root = nn(10);
    root->left = nn(5); root->right = nn(15);
    root->left->left = nn(2);
    printf("nodes=%d height=%d\n", count(root), height(root));
    return 0;
}

Szybkie sprawdzenie

Sprawdź, jak dobrze rozumieją Państwo strukturę węzła.

Podsumowanie

Węzeł drzewa binarnego przechowuje wartość oraz dwa wskaźniki do tego samego typu (left, right), ustawione na NULL, gdy dzieci nie istnieją.

Alokujemy węzły za pomocą malloc, ręcznie je łączymy i przetwarzamy rekurencyjnie. Sprawdzenie NULL jest zawsze przypadkiem bazowym przy zliczaniu, obliczaniu wysokości i rozpoznawaniu liści.

Często zadawane pytania

Czy lekcja „Węzły i struktura drzewa” jest bezpłatna?

Tak — pełny tekst „Węzły i struktura 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 „Węzły i struktura drzewa”?

Zam modeluje Pan/Pani węzeł za pomocą wskaźników. Ć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 1 z 4.

Ile czasu zajmuje lekcja „Węzły i struktura 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

  1. Węzły i struktura drzewa
  2. Wstawianie do BST
  3. Przechodzenie drzewa
  4. Wyszukiwanie i zwalnianie pamięci
← Powrót do C Academy