Двоични дървета в C: Пълно ръководство за начинаещи

Информатек Дигитал » Алгоритмос » Двоични дървета в C: Пълно ръководство за начинаещи

Добре дошли в това изчерпателно ръководство за двоични дървета в C. В тази статия ще разгледаме основите на двоичните дървета и как да ги внедрим в езика за програмиране C. Ако сте начинаещ в програмирането или просто искате да подобрите своите C умения, това ръководство е за вас.

Бинарните дървета са фундаментални структури от данни в компютърните науки и се използват в широк спектър от приложения. Разбирането на това как работят и как да ги имплементирате ще ви помогне да решавате сложни проблеми по-ефективно и елегантно.

В тази статия ще разгледаме основите на двоичните дървета, включително тяхната структура, вмъкване и изтриване на възли, обхождане и търсене на елементи. Ще предоставим и практически примери на езика за програмиране C, за да видите как тези концепции се прилагат на практика.

Така че да започваме!

Какво представляват двоичните дървета?

Двоичните дървета са йерархични структури от данни, съставени от взаимосвързани възли. Всеки възел може да има до два дъщерни възела: един отляво и един отдясно. Тази структура с два клона е това, което отличава двоичните дървета от другите структури от данни.

В едно двоично дърво първият възел се нарича основен възел. Дъщерните възли се наричат ​​дъщерни възли, а възлите без деца се наричат ​​листови възли. Възлите на едно и също ниво се наричат ​​братски възли.

Предимства на двоичните дървета

Двоичните дървета предлагат няколко предимства по отношение на ефективното съхранение и търсене на данни. Някои от основните предимства включват:

1. Ефективно търсенеДвоичните дървета позволяват елементите да се търсят по време на изпълнение по-бързо от други структури от данни, като например свързани списъци. Това се дължи на йерархичната структура на дървото и способността му бързо да разделя набора от данни.
2. Гъвкаво поставяне и отстраняванеДвоичните дървета са силно адаптивни към операции за вмъкване и изтриване на възли. За разлика от статичните структури от данни като масиви, двоичните дървета могат да растат и да променят структурата си динамично.
3. Представяне на йерархични връзкиДвоичните дървета са особено полезни за представяне на йерархични връзки между елементи. Например, в структура на файлова директория, всяка директория може да бъде представена като възел в дървото, с поддиректории и файлове като нейни дъщерни възли.

Структура на двоично дърво

Преди да се потопим в реализацията на двоични дървета в 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;
}

Тази функция получава указател към корена на дървото и стойността на възела за вмъкване. Ако коренът е нула, това означава, че дървото е празно и създаваме нов възел в корена. В противен случай сравняваме стойността на възела със стойността на корена и решаваме дали да вмъкнем възела отляво или отдясно.

Изтриване на възли

Изтриването на възли в двоично дърво може да бъде малко по-сложно. Зависи от няколко случая, като например дали възелът, който трябва да бъде изтрит, има деца или не. По-долу е 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);
    }
}

Тази функция извършва рекурсивно търсене в двоичното дърво. Ако стойността на текущия възел е равна на търсената стойност, възелът се връща. В противен случай лявото или дясното поддърво се търси въз основа на стойността и процесът се повтаря, докато се намери стойността или се достигне нулев възел.

Примери за внедряване на двоични дървета в 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. Как мога да премахна определен възел от двоично дърво?

За да премахнете конкретен възел от двоично дърво, трябва да изпълните следните стъпки:

1. Намерете възела, който искате да изтриете, като използвате дървовидно търсене.
2. Разгледайте различните случаи на елиминиране:
   • Ако възелът няма деца, можете просто да го изтриете и да освободите паметта му.
   • Ако възелът има само едно дете, можете да замените възела с неговото дете.
   • Ако възелът има две деца, трябва да намерите най-близкия наследник (най-малкия възел в дясното поддърво) и да замените стойността на възела, който трябва да бъде изтрит, със стойността на наследника. След това премахнете наследника от дървото.
3. Коригира връзките и указателите според нуждите, за да поддържа правилната дървовидна структура.

4. Какво е пълно двоично дърво?

Пълното двоично дърво е специален тип двоично дърво, в което всички нива, с изключение на евентуално последното, са напълно запълнени, а възлите на последното ниво са разположени възможно най-вляво. Това означава, че всички възли имат две деца, с изключение на възлите на последното ниво, които могат да имат едно или нито едно дете.

5. Каква е височината на двоичното дърво?

Височината на едно двоично дърво е дължината на най-дългия път от корена до листа. С други думи, това е максималният брой ръбове между корена и всеки лист в дървото. Височината се измерва като брой нива, така че дърво само с един възел има височина 0, а празно дърво няма височина.

6. Кога трябва да използвам двоично дърво в моите програми?

Двоичните дървета са полезни в различни ситуации. Някои често срещани случаи, в които можете да използвате двоични дървета, включват:

• Ефективно търсене на елементи: Ако трябва бързо да търсите елементи в структура от данни, двоично дърво може да осигури ефективен достъп до данните.
• Представяне на йерархични връзки: Двоичните дървета са идеални за представяне на йерархични връзки, като структурата на директорията в файлова система.
• Сортиране на данни: Можете да използвате дървета за двоично търсене за ефективно сортиране на данни и извършване на търсения, вмъквания и изтривания в логаритмично време.

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

Заключение

В това изчерпателно ръководство ние проучихме основните концепции на двоичните дървета в C. Научихме за тяхната структура, как да вмъкваме и премахваме възли, да извършваме обхождания и да търсим елементи в двоично дърво.

Надяваме се, че това ръководство ви е дало солидно разбиране за двоичните дървета и как да ги внедрите в C. Двоичните дървета са многостранни и мощни структури от данни, които могат да ви помогнат да решите широк кръг от проблеми в програмирането.

Не забравяйте да практикувате и експериментирате с предоставените примери, за да засилите разбирането си за двоичните дървета в C. Успех в обучението и разработването на софтуер!