Бінарні дерева в C: повний посібник для початківців

Інформатек Діджитал » Алгоритми » Бінарні дерева в C: повний посібник для початківців

Ієрархічна структура з вузлами, що мають максимум двох дочірніх вузлів; включає корінь, листя та рівні.
Переваги: ефективний пошук та вставка, ієрархічні представлення та динамічна гнучкість порівняно з масивами.
Ключові операції: обходи (вхідні, попередні, кінцеві), пошук, вставка та видалення для сортування та керування даними.

Ласкаво просимо до цього вичерпного посібника з бінарних дерев у C. У цій статті ми розглянемо основи бінарних дерев і як їх реалізувати на мові програмування C. Якщо ви новачок у програмуванні або просто хочете вдосконалити свої навички C, цей посібник для вас.

Бінарні дерева – це фундаментальні структури даних в інформатиці, які використовуються в широкому спектрі застосувань. Розуміння того, як вони працюють і як їх реалізувати, допоможе вам вирішувати складні проблеми ефективніше та елегантніше.

У цій статті ми розглянемо основи бінарних дерев, включаючи їх структуру, вставку та видалення вузлів, обхід та пошук елементів. Ми також наведемо практичні приклади мовою програмування C , щоб ви могли побачити, як ці концепції застосовуються на практиці.

Тож почнемо!

Що таке бінарні дерева?

Бінарні дерева — це ієрархічні структури даних, що складаються із взаємопов’язаних вузлів. Кожен вузол може мати до двох дочірніх вузлів: один ліворуч і один праворуч. Ця структура з двома гілками є те, що відрізняє двійкові дерева від інших структур даних.

У бінарному дереві перший вузол називається кореневим вузлом. Дочірні вузли називаються дочірніми вузлами, а вузли без дочірніх елементів — листовими вузлами. Вузли одного рівня називаються однорідними вузлами.

Переваги бінарних дерев

Бінарні дерева пропонують кілька переваг щодо ефективного зберігання та пошуку даних. Деякі з ключових переваг включають:

Ефективний пошукДвійкові дерева дозволяють шукати елементи під час виконання швидше, ніж інші структури даних, такі як пов’язані списки. Це пов’язано з ієрархічною структурою дерева та його здатністю швидко розділяти набір даних.
Гнучке введення та видаленняДвійкові дерева добре адаптуються до операцій вставки та видалення вузлів. На відміну від статичних структур даних, таких як масиви, бінарні дерева можуть рости та динамічно змінювати свою структуру.
Представлення ієрархічних відносинБінарні дерева особливо корисні для представлення ієрархічних зв’язків між елементами. Наприклад, у структурі файлового каталогу кожен каталог може бути представлений як вузол у дереві з підкаталогами та файлами як дочірніми вузлами.

Структура бінарного дерева

Перш ніж ми заглибимося в реалізацію бінарних дерев у C, важливо зрозуміти їхню базову структуру. Кожен вузол у бінарному дереві містить значення та посилання на його лівий і правий дочірні вузли, якщо вони є.

У наведеній нижче таблиці показано структуру вузла бінарного дерева:

Двійковий вузол
доблесть
Лівий вузол
Правий вузол

Кожен вузол може зберігати будь-які типи даних, такі як цілі числа, символи або більш складні структури. Кореневий вузол є початковою точкою дерева, і з нього ми можемо отримати доступ до всіх інших вузлів.

Реалізація бінарних дерев у C

Тепер, коли ми маємо базове розуміння бінарних дерев, настав час реалізувати їх мовою програмування C. Далі ми побачимо, як оголошувати та використовувати структуру бінарного дерева в C.

Оголошення структури бінарного дерева

У C ми можемо оголосити структуру бінарного дерева за допомогою структури та покажчиків. Ось основна декларація структури:

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

У цій структурі valor представляє значення, що зберігається у вузлі, і izquierdo y derecho є покажчиками на лівий і правий дочірні вузли відповідно.

Алгоритм Гровера: революція пошуку за допомогою квантових обчислень

Створення нового вузла

Щоб створити новий вузол у бінарному дереві, нам потрібно виділити пам’ять для вузла та встановити його значення. Ось функція C, яка створює новий вузол:

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;
}

Функція malloc Він використовується для виділення динамічної пам'яті вузлу. Потім ми встановлюємо значення вузла і повертаємо створений вузол.

Вставлення вузлів

Вставка вузлів є фундаментальним процесом у бінарних деревах. Дозволяє додавати нові елементи до дерева в правильному місці на основі значення вузла. Нижче наведено функцію C для вставки вузла в бінарне дерево:

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;
}

Ця функція отримує вказівник на корінь дерева та значення вузла для вставки. Якщо root дорівнює нулю, це означає, що дерево порожнє, і ми створюємо новий вузол у корені. В іншому випадку ми порівнюємо значення вузла зі значенням кореня і вирішуємо, вставляти вузол ліворуч чи праворуч.

Видалення вузлів

Видалення вузлів у бінарному дереві може бути дещо складнішим. Це залежить від кількох випадків, наприклад, чи має вузол, який потрібно видалити, дітей чи ні. Нижче наведено функцію C для видалення вузла у бінарному дереві:

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;
}

У цій функції ми перевіряємо, чи значення вузла менше, більше або дорівнює значенню поточного кореня. Залежно від конкретного випадку ми проводимо наступні дії:

Якщо значення менше, йдемо ліворуч від дерева.
Якщо значення більше, йдемо праворуч від дерева.
Якщо значення дорівнює, ми знаходимо найближчого наступника вузла (найменший вузол у правому піддереві) і замінюємо його поточним вузлом. Потім видаляємо наступника з правого піддерева.

Обходи в бінарних деревах

Обходи — це операції, які дозволяють відвідувати всі вузли бінарного дерева в певному порядку. Існує три поширених типи турів:

Порядковий обхід : Спочатку відвідує ліве піддерево, потім поточний вузол і, нарешті, праве піддерево. Ось функція на C, яка виконує попорядковий обхід бінарного дерева:

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

Попередній обхід : Спочатку відвідує поточний вузол, потім ліве піддерево і, нарешті, праве піддерево. Ось функція на C, яка виконує попередній обхід бінарного дерева:

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

Обхід після порядку : Спочатку відвідує ліве піддерево, потім праве піддерево і, нарешті, поточний вузол. Ось функція C, яка виконує обхід після порядку бінарного дерева:

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

Пошук елементів

Пошук елементів у двійковому дереві дозволяє швидко знайти конкретне значення в структурі даних. Ось функція C для пошуку елемента у двійковому дереві:

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);
    }
}

Ця функція виконує рекурсивний пошук у бінарному дереві. Якщо значення поточного вузла дорівнює шуканому значенню, повертається вузол. В іншому випадку шукається ліве або праве піддерево на основі значення, і процес повторюється, доки не буде знайдено значення або не досягнуто нульового вузла.

Структури даних у програмуванні: The Ultimate Guide

Приклади реалізації бінарних дерев у C

Тепер, коли ми розглянули основи бінарних дерев і те, як їх реалізувати в C, давайте розглянемо кілька практичних прикладів.

Приклад 1: Створення бінарного дерева

Припустімо, ми хочемо створити бінарне дерево з такими значеннями: 10, 5, 15, 3, 7, 13, 18. Ось як ми можемо це зробити в 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;
}

У цьому прикладі ми створюємо вказівник на корінь дерева, а потім використовуємо функцію insertarNodo щоб додати значення до дерева.

Приклад 2: Порядковий обхід бінарного дерева

Щоб надрукувати значення двійкового дерева по порядку, ми можемо викликати функцію inOrden наступним чином:

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

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

    return 0;
}

Цей приклад надрукує значення в дереві в порядку зростання.

Часті запитання

1. Яка різниця між бінарним деревом і бінарним деревом пошуку?

Двійкове дерево пошуку (BST) - це особливий тип бінарного дерева, в якому елементи розташовані так, що менші значення знаходяться зліва, а більші значення - справа. Це забезпечує більш ефективний пошук елементів порівняно зі звичайним бінарним деревом.

2. Чи можу я мати вузли з повторюваними значеннями у бінарному дереві?

Так, у бінарному дереві можуть бути вузли з повторюваними значеннями. Однак, залежно від реалізації та конкретних правил бінарного дерева, можуть існувати різні способи роботи з повторюваними вузлами. Деякі реалізації можуть дозволяти дублікати та зберігати їх у будь-якому порядку, тоді як інші можуть вимагати, щоб повторювані значення оброблялися спеціально або відкидалися.

3. Як я можу видалити певний вузол із бінарного дерева?

Щоб видалити певний вузол із бінарного дерева, потрібно виконати такі дії:

Знайдіть вузол, який потрібно видалити, за допомогою пошуку в ієрархії.
Розглянемо різні випадки усунення:
- Якщо у вузла немає дітей, ви можете просто видалити його та звільнити його пам'ять.
- Якщо вузол має лише одного дочірнього вузла, ви можете замінити вузол його дочірнім вузлом.
- Якщо вузол має двох дочірніх вузлів, ви повинні знайти найближчого наступника (найменший вузол у правому піддереві) і замінити значення вузла, який потрібно видалити, значенням наступника. Потім видаліть наступника з дерева.
За потреби коригує посилання та покажчики для підтримки правильної деревовидної структури.

Вивчення алгоритму «перший прийшов, перший обслужений».

4. Що таке повне бінарне дерево?

Повне бінарне дерево — це особливий тип бінарного дерева, в якому всі рівні, крім, можливо, останнього, повністю заповнені, а вузли останнього рівня розташовані якомога ліворуч. Це означає, що всі вузли мають двох дочірніх вузлів, за винятком, можливо, вузлів останнього рівня, які можуть мати одного дочірнього елемента або не мати жодного.

5. Що таке висота бінарного дерева?

Висота бінарного дерева - це довжина найдовшого шляху від кореня до листа. Іншими словами, це максимальна кількість ребер між коренем і будь-яким листом дерева. Висота вимірюється кількістю рівнів, тому дерево лише з одним вузлом має висоту 0, а порожнє дерево не має висоти.

6. Коли я повинен використовувати бінарне дерево у своїх програмах?

Бінарні дерева корисні в різних ситуаціях. Деякі поширені випадки, коли ви можете використовувати двійкові дерева, включають:

Ефективний пошук елементів: якщо вам потрібно швидко знайти елементи в структурі даних, бінарне дерево може забезпечити ефективний доступ до даних.
Представлення ієрархічних зв’язків: двійкові дерева ідеально підходять для представлення ієрархічних зв’язків, таких як структура каталогів у файлова система.
Сортування даних. Ви можете використовувати двійкові дерева пошуку для ефективного сортування даних і виконання пошуку, вставки та видалення за логарифмічний час.

Не забудьте оцінити свої вимоги та врахувати складність операцій над бінарними деревами, перш ніж вирішити використовувати їх у своїх програмах.

Висновок

У цьому вичерпному посібнику ми дослідили фундаментальні концепції бінарних дерев у C. Ми дізналися про їх структуру, як вставляти та видаляти вузли, виконувати обхід і шукати елементи у бінарному дереві.

Ми сподіваємося, що цей посібник дав вам чітке розуміння бінарних дерев і того, як їх реалізувати в C. Бінарні дерева — це універсальні та потужні структури даних, які можуть допомогти вам вирішити широкий спектр проблем у програмуванні.

Не забувайте практикуватися та експериментувати з наданими прикладами, щоб зміцнити ваше розуміння бінарних дерев у C. Успіхів у вашому дослідженні та розробці програмного забезпечення!