Drzewa binarne w języku C: kompletny przewodnik dla początkujących

Informatec Digital » Algorytmy » Drzewa binarne w języku C: kompletny przewodnik dla początkujących

Witamy w tym kompleksowym przewodniku po drzewach binarnych w języku C. W tym artykule przyjrzymy się podstawom drzew binarnych i sposobom ich implementacji w języku programowania C. Jeśli jesteś początkującym programistą lub po prostu chcesz poprawić swoje umiejętności w zakresie języka C, ten przewodnik jest dla Ciebie.

Drzewa binarne to fundamentalne struktury danych w informatyce, wykorzystywane w szerokim zakresie zastosowań. Zrozumienie ich działania i sposobów implementacji pomoże Ci rozwiązywać złożone problemy sprawniej i bardziej elegancko.

W tym artykule omówimy podstawy drzew binarnych, w tym ich strukturę, wstawianie i usuwanie węzłów, przechodzenie między nimi oraz wyszukiwanie elementów. Przedstawimy również praktyczne przykłady w języku programowania C , aby pokazać, jak te koncepcje sprawdzają się w praktyce.

Więc zacznijmy!

Czym są drzewa binarne?

Drzewa binarne to hierarchiczne struktury danych składające się z połączonych ze sobą węzłów. Każdy węzeł może mieć maksymalnie dwa węzły podrzędne: jeden po lewej i jeden po prawej. Ta dwugałęziowa struktura odróżnia drzewa binarne od innych struktur danych.

W drzewie binarnym pierwszy węzeł nazywany jest węzłem głównym. Węzły podrzędne nazywane są węzłami podrzędnymi, a węzły bez dzieci nazywane są węzłami liściowymi. Węzły na tym samym poziomie nazywane są węzłami siostrzanymi.

Korzyści z drzew binarnych

Drzewa binarne oferują szereg zalet pod względem efektywnego przechowywania i wyszukiwania danych. Do najważniejszych korzyści należą:

1. Efektywne wyszukiwanieDrzewa binarne pozwalają na szybsze przeszukiwanie elementów w czasie wykonywania niż inne struktury danych, takie jak listy powiązane. Wynika to z hierarchicznej struktury drzewa i jego możliwości szybkiego partycjonowania zbioru danych.
2. Elastyczne wkładanie i wyjmowanieDrzewa binarne są wyjątkowo przydatne do operacji wstawiania i usuwania węzłów. W przeciwieństwie do statycznych struktur danych, takich jak tablice, drzewa binarne mogą rosnąć i zmieniać swoją strukturę dynamicznie.
3. Reprezentacja relacji hierarchicznychDrzewa binarne są szczególnie przydatne do przedstawiania hierarchicznych relacji między elementami. Na przykład w strukturze katalogów plików każdy katalog może być reprezentowany jako węzeł w drzewie, a podkatalogi i pliki jako jego węzły podrzędne.

Struktura drzewa binarnego

Zanim zagłębimy się w implementację drzew binarnych w języku C, istotne jest zrozumienie ich podstawowej struktury. Każdy węzeł w drzewie binarnym zawiera wartość i odwołania do swoich węzłów podrzędnych (lewego i prawego), jeśli takie istnieją.

Poniższa tabela przedstawia strukturę węzła w drzewie binarnym:

Węzeł binarny
Dzielność
Węzeł lewy
Węzeł prawy

Każdy węzeł może przechowywać dowolny typ danych, np. liczby całkowite, znaki lub bardziej złożone struktury. Węzeł główny jest punktem początkowym drzewa. Z niego możemy uzyskać dostęp do wszystkich pozostałych węzłów.

Implementacja drzew binarnych w C

Skoro mamy już podstawową wiedzę na temat drzew binarnych, czas zaimplementować je w języku programowania C. Następnie zobaczymy, jak deklarować i używać struktury drzewa binarnego w C.

Deklarowanie struktury drzewa binarnego

W języku C możemy zadeklarować strukturę drzewa binarnego za pomocą struktury i wskaźników. Oto podstawowa deklaracja struktury:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

W tej strukturze, valor reprezentuje wartość przechowywaną w węźle i izquierdo y derecho są wskaźnikami odpowiednio do węzłów podrzędnych lewego i prawego.

Tworzenie nowego węzła

Aby utworzyć nowy węzeł w drzewie binarnym, musimy przydzielić węzłowi pamięć i ustawić jego wartości. Oto funkcja C, która tworzy nowy węzeł:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

Funkcja malloc Służy do przydzielania pamięci dynamicznej węzłowi. Następnie ustawiamy wartości węzłów i zwracamy utworzony węzeł.

Wstawianie węzłów

Wstawianie węzłów jest podstawowym procesem w drzewach binarnych. Umożliwia dodawanie nowych elementów do drzewa w odpowiednim miejscu, na podstawie wartości węzła. Poniżej znajduje się funkcja języka C służąca do wstawiania węzła do drzewa binarnego:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Funkcja ta otrzymuje wskaźnik do korzenia drzewa i wartość węzła, który ma zostać wstawiony. Jeśli korzeń jest pusty, oznacza to, że drzewo jest puste i tworzymy nowy węzeł u korzenia. W przeciwnym wypadku porównujemy wartość węzła z wartością korzenia i decydujemy, czy wstawić węzeł po lewej czy po prawej stronie.

Usuwanie węzłów

Usuwanie węzłów w drzewie binarnym może być nieco bardziej skomplikowane. Zależy to od kilku czynników, na przykład od tego, czy węzeł przeznaczony do usunięcia ma potomków, czy nie. Poniżej znajduje się funkcja języka C służąca do usuwania węzła w drzewie binarnym:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

W tej funkcji sprawdzamy, czy wartość węzła jest mniejsza, większa czy równa wartości bieżącego pierwiastka. W zależności od przypadku podejmujemy następujące działania:

• Jeżeli wartość jest mniejsza, przechodzimy na lewą stronę drzewa.
• Jeżeli wartość jest większa, przechodzimy na prawą stronę drzewa.
• Jeżeli wartość jest równa, znajdujemy najbliższego następcę węzła (najmniejszy węzeł w prawym poddrzewie) i zastępujemy go bieżącym węzłem. Następnie usuwamy następnik z prawego poddrzewa.

Przejścia w drzewach binarnych

Przejścia to operacje pozwalające odwiedzić wszystkie węzły drzewa binarnego w określonej kolejności. Istnieją trzy najpopularniejsze rodzaje wycieczek:

Przechodzenie w kolejności : Najpierw odwiedza lewe poddrzewo, następnie bieżący węzeł, a na końcu prawe poddrzewo. Oto funkcja języka C, która wykonuje przechodzenie w kolejności drzewa binarnego:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Przechodzenie w kolejności pre-order : Najpierw odwiedza bieżący węzeł, następnie lewe poddrzewo, a na końcu prawe poddrzewo. Oto funkcja języka C, która wykonuje przechodzenie w kolejności pre-order drzewa binarnego:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Przechodzenie w kolejności potomnej : najpierw odwiedza lewe poddrzewo, następnie prawe poddrzewo, a na końcu bieżący węzeł. Oto funkcja C, która wykonuje przechodzenie w kolejności potomnej drzewa binarnego:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Wyszukaj elementy

Przeszukiwanie elementów drzewa binarnego umożliwia szybkie odnalezienie konkretnej wartości w strukturze danych. Oto funkcja języka C umożliwiająca wyszukiwanie elementów w drzewie binarnym:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Funkcja ta wykonuje rekurencyjne wyszukiwanie w drzewie binarnym. Jeżeli wartość bieżącego węzła jest równa wartości wyszukiwanej, węzeł jest zwracany. W przeciwnym wypadku przeszukiwane jest lewe lub prawe poddrzewo na podstawie wartości, a proces jest powtarzany aż do znalezienia wartości lub osiągnięcia węzła pustego.

Przykłady implementacji drzew binarnych w języku C

Teraz, gdy poznaliśmy podstawy drzew binarnych i sposób ich implementacji w języku C, przyjrzyjmy się kilku praktycznym przykładom.

Przykład 1: Tworzenie drzewa binarnego

Załóżmy, że chcemy utworzyć drzewo binarne o następujących wartościach: 10, 5, 15, 3, 7, 13, 18. Oto jak możemy to zrobić w języku C:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

W tym przykładzie tworzymy wskaźnik do korzenia drzewa, a następnie używamy funkcji insertarNodo aby dodać wartości do drzewa.

Przykład 2: Przechodzenie drzewa binarnego w kolejności

Aby wydrukować wartości drzewa binarnego w kolejności, możemy wywołać funkcję inOrden następująco:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Ten przykład wydrukuje wartości w drzewie w kolejności rosnącej.

Najczęściej zadawane pytania

1. Jaka jest różnica pomiędzy drzewem binarnym a drzewem poszukiwań binarnych?

Drzewo poszukiwań binarnych (BST) to specjalny typ drzewa binarnego, w którym elementy są ułożone tak, że mniejsze wartości znajdują się po lewej stronie, a większe po prawej. Umożliwia to efektywniejsze przeszukiwanie elementów w porównaniu do zwykłego drzewa binarnego.

2. Czy w drzewie binarnym mogą znajdować się węzły o powtarzających się wartościach?

Tak, w drzewie binarnym możliwe jest występowanie węzłów o powtarzających się wartościach. Jednak w zależności od implementacji i konkretnych reguł drzewa binarnego, mogą istnieć różne sposoby radzenia sobie z duplikatami węzłów. Niektóre implementacje mogą dopuszczać duplikaty i przechowywać je w dowolnej kolejności, podczas gdy inne mogą wymagać specjalnego traktowania wartości duplikatów lub ich usuwania.

3. Jak mogę usunąć konkretny węzeł z drzewa binarnego?

Aby usunąć konkretny węzeł z drzewa binarnego, należy wykonać następujące kroki:

1. Znajdź węzeł, który chcesz usunąć, korzystając z wyszukiwania w drzewie.
2. Rozważ różne przypadki eliminacji:
   • Jeżeli węzeł nie ma żadnych dzieci, możesz go po prostu usunąć i zwolnić jego pamięć.
   • Jeśli węzeł ma tylko jedno dziecko, możesz zastąpić węzeł jego dzieckiem.
   • Jeśli węzeł ma dwoje dzieci, należy znaleźć najbliższego następcę (najmniejszy węzeł w prawym poddrzewie) i zastąpić wartość węzła, który ma zostać usunięty, wartością następcy. Następnie usuń następnik z drzewa.
3. Dostosowuje łącza i wskaźniki w celu zachowania prawidłowej struktury drzewa.

4. Czym jest pełne drzewo binarne?

Pełne drzewo binarne to szczególny typ drzewa binarnego, w którym wszystkie poziomy, z wyjątkiem ostatniego, są całkowicie wypełnione, a węzły ostatniego poziomu znajdują się tak daleko na lewo, jak to możliwe. Oznacza to, że wszystkie węzły mają dwoje dzieci, z wyjątkiem węzłów na ostatnim poziomie, które mogą mieć jedno dziecko lub nie mieć go wcale.

5. Jaka jest wysokość drzewa binarnego?

Wysokość drzewa binarnego to długość najdłuższej ścieżki od korzenia do liścia. Innymi słowy, jest to maksymalna liczba krawędzi pomiędzy korzeniem i dowolnym liściem w drzewie. Wysokość mierzona jest liczbą poziomów, zatem drzewo posiadające tylko jeden węzeł ma wysokość równą 0, a puste drzewo nie ma wysokości.

6. Kiedy powinienem używać drzewa binarnego w swoich programach?

Drzewa binarne są przydatne w wielu sytuacjach. Oto kilka typowych przypadków, w których można wykorzystać drzewa binarne:

• Efektywne wyszukiwanie elementów: Jeśli musisz szybko wyszukać elementy w strukturze danych, drzewo binarne może zapewnić efektywny dostęp do danych.
• Reprezentowanie relacji hierarchicznych: Drzewa binarne idealnie nadają się do reprezentowania relacji hierarchicznych, takich jak struktura katalogów w pliku. system plików.
• Sortowanie danych: Można używać drzew wyszukiwania binarnego do efektywnego sortowania danych oraz wykonywania wyszukiwań, wstawiania i usuwania w czasie logarytmicznym.

Pamiętaj, aby ocenić swoje wymagania i wziąć pod uwagę złożoność operacji na drzewach binarnych, zanim zdecydujesz się na ich użycie w swoich programach.

Wnioski

W tym kompleksowym przewodniku przyjrzeliśmy się podstawowym koncepcjom drzew binarnych w języku C. Poznaliśmy ich strukturę, dowiedzieliśmy się, jak wstawiać i usuwać węzły, wykonywać przejścia i wyszukiwać elementy w drzewie binarnym.

Mamy nadzieję, że ten przewodnik zapewnił Ci solidną wiedzę na temat drzew binarnych i sposobu ich implementacji w języku C. Drzewa binarne to wszechstronne i potężne struktury danych, które mogą pomóc w rozwiązaniu szerokiego zakresu problemów programistycznych.

Pamiętaj o ćwiczeniu i eksperymentowaniu z podanymi przykładami, aby pogłębić swoją wiedzę na temat drzew binarnych w języku C. Powodzenia w nauce i rozwijaniu oprogramowania!