Бинарна стабла у Ц: Потпуни водич за почетнике

Последње ажурирање: КСНУМКС Јануар КСНУМКС
Аутор: ТецноДигитал
  • Хијерархијска структура са чворовима који имају највише два потомка; укључује корен, листове и нивое.
  • Предности: ефикасне претраге и уметања, хијерархијске репрезентације и динамичка флексибилност у поређењу са низовима.
  • Кључне операције: обиласци (у, пре, после), претрага, уметање и брисање ради сортирања и управљања подацима.
Бинарна стабла у Ц

Добродошли у овај свеобухватан водич о бинарним стаблима у Ц. У овом чланку ћемо истражити основе бинарних стабала и како их имплементирати у програмском језику Ц Ако сте почетник у програмирању или само желите да побољшате своје Ц вештине, овај водич је за вас.

Бинарна стабла су фундаменталне структуре података у рачунарству и користе се у широком спектру примена. Разумевање како функционишу и како их имплементирати помоћи ће вам да ефикасније и елегантније решавате сложене проблеме.

У овом чланку ћемо истражити основе бинарних стабала, укључујући њихову структуру, уметање и брисање чворова, пролазак кроз њих и претрагу елемената. Такође ћемо пружити практичне примере у програмском језику C како бисте могли да видите како се ови концепти примењују у пракси.

Па хајде да почнемо!

Шта су бинарна стабла?

Бинарна стабла су хијерархијске структуре података састављене од међусобно повезаних чворова. Сваки чвор може имати до два подређена чвора: један са леве стране и један са десне стране. Ова структура са две гране је оно што разликује бинарна стабла од других структура података.

У бинарном стаблу, први чвор се назива коренски чвор. Подређени чворови се називају подређени чворови, а чворови без деце се називају лисни чворови. Чворови на истом нивоу се називају братски и сестрински чворови.

Предности бинарних стабала

Бинарна стабла нуде неколико предности у смислу ефикасног складиштења и претраживања података. Неке од кључних предности укључују:

  1. Ефикасна претрагаБинарна стабла омогућавају да се елементи претражују у току извођења брже од других структура података, као што су повезане листе. Ово је због хијерархијске структуре стабла и његове способности да брзо подели скуп података.
  2. Флексибилно уметање и уклањањеБинарна стабла су веома прилагодљива операцијама уметања и брисања чворова. За разлику од статичких структура података као што су низови, бинарна стабла могу да расту и динамички мењају своју структуру.
  3. Представљање хијерархијских односаБинарна стабла су посебно корисна за представљање хијерархијских односа између елемената. На пример, у структури директоријума датотека, сваки директоријум може бити представљен као чвор у стаблу, са поддиректоријумима и датотекама као подређеним чворовима.

Структура бинарног стабла

Пре него што заронимо у имплементацију бинарних стабала у Ц, важно је разумети њихову основну структуру. Сваки чвор у бинарном стаблу садржи вредност и референце на његов леви и десни подређени чвор, ако их има.

Следећа табела приказује структуру чвора у бинарном стаблу:

Бинарни чвор
храброст
Леви чвор
Десни чвор

Сваки чвор може да складишти било коју врсту података, као што су цели бројеви, знакови или сложеније структуре. Коренски чвор је почетна тачка стабла и из њега можемо приступити свим осталим чворовима.

Имплементација бинарних стабала у Ц

Сада када имамо основно разумевање бинарних стабала, време је да их имплементирамо у програмском језику C. Затим ћемо видети како да декларишемо и користимо бинарну структуру стабла у C-у.

Декларисање структуре бинарног стабла

У Ц-у можемо декларисати структуру бинарног стабла користећи структуру и показиваче. Ево основне декларације структуре:

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

У овој структури, valor представља вредност ускладиштену у чвору, и izquierdo y derecho су показивачи на леви и десни подређени чвор, респективно.

  Главне врсте алгоритма објашњене на једноставан начин

Креирање новог чвора

Да бисмо креирали нови чвор у бинарном стаблу, потребно је да доделимо меморију за чвор и поставимо његове вредности. Ево Ц функције која креира нови чвор:

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 Користи се за додељивање динамичке меморије чвору. Затим постављамо вредности чвора и враћамо креирани чвор.

Уметање чворова

Уметање чворова је основни процес у бинарном дрвећу. Омогућава вам да додате нове елементе стаблу на исправној позицији на основу вредности чвора. Испод је Ц функција за уметање чвора у бинарно стабло:

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

Ова функција прима показивач на корен стабла и вредност чвора за уметање. Ако је корен нула, то значи да је дрво празно и да креирамо нови чвор у корену. У супротном, поредимо вредност чвора са вредношћу корена и одлучујемо да ли да убацимо чвор лево или десно.

Брисање чворова

Брисање чворова у бинарном стаблу може бити мало сложеније. Зависи од неколико случајева, као што је да ли чвор који се брише има деце или не. Испод је Ц функција за брисање чвора у бинарном стаблу:

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

Потражите елементе

Тражење елемената у бинарном стаблу омогућава нам да брзо пронађемо одређену вредност унутар структуре података. Ево Ц функције за тражење елемента у бинарном стаблу:

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

Ова функција врши рекурзивну претрагу у бинарном стаблу. Ако је вредност тренутног чвора једнака траженој вредности, чвор се враћа. У супротном, лево или десно подстабло се претражује на основу вредности и процес се понавља док се вредност не пронађе или док се не достигне нулти чвор.

  Структуре података и алгоритми: комплетан водич за програмере

Примери имплементације бинарних стабала у Ц

Сада када смо покрили основе бинарних стабала и како их имплементирати у Ц, погледајмо неколико практичних примера.

Пример 1: Креирање бинарног стабла

Претпоставимо да желимо да креирамо бинарно стабло са следећим вредностима: 10, 5, 15, 3, 7, 13, 18. Ево како то можемо да урадимо у Ц:

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. Која је разлика између бинарног стабла и бинарног стабла претраге?

Бинарно стабло претраге (БСТ) је посебна врста бинарног стабла у којој су елементи распоређени тако да су мање вредности на левој, а веће вредности на десној страни. Ово омогућава ефикасније претраживање елемената у поређењу са обичним бинарним стаблом.

2. Могу ли да имам чворове са дуплираним вредностима у бинарном стаблу?

Да, могуће је имати чворове са дуплираним вредностима у бинарном стаблу. Међутим, у зависности од имплементације и специфичних правила бинарног стабла, могу постојати различити начини за решавање дуплих чворова. Неке имплементације могу дозволити дупликате и ускладиштити их било којим редоследом, док друге могу захтевати да се дупликати вредности посебно обрађују или одбацују.

3. Како могу да уклоним одређени чвор из бинарног стабла?

Да бисте уклонили одређени чвор из бинарног стабла, потребно је да пратите ове кораке:

  1. Пронађите чвор који желите да избришете користећи претрагу стабла.
  2. Размотрите различите случајеве елиминације:
    • Ако чвор нема деце, можете га једноставно избрисати и ослободити његову меморију.
    • Ако чвор има само једно дете, можете га заменити његовим дететом.
    • Ако чвор има два детета, морате пронаћи најближег наследника (најмањи чвор у десном подстаблу) и заменити вредност чвора који треба да се избрише вредношћу наследника. Затим уклоните наследника са стабла.
  3. Прилагођава везе и показиваче по потреби за одржавање исправне структуре стабла.
  Генетски алгоритми: концепт и примене

4. Шта је пуно бинарно стабло?

Пуно бинарно стабло је посебна врста бинарног стабла у којој су сви нивои, осим евентуално последњег, потпуно попуњени, а чворови последњег нивоа се налазе што је више могуће лево. То значи да сви чворови имају по два детета, осим евентуално чворова на последњем нивоу, који могу имати једно или ниједно потомство.

5. Колика је висина бинарног дрвета?

Висина бинарног дрвета је дужина најдуже стазе од корена до листа. Другим речима, то је максималан број ивица између корена и било ког листа на дрвету. Висина се мери бројем нивоа, тако да дрво са само једним чвором има висину 0, а празно дрво нема висину.

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

Бинарна стабла су корисна у разним ситуацијама. Неки уобичајени случајеви у којима можете користити бинарна стабла укључују:

  • Ефикасно тражење елемената: Ако требате брзо да потражите елементе у структури података, бинарно стабло може да обезбеди ефикасан приступ подацима.
  • Представљање хијерархијских односа: Бинарна стабла су идеална за представљање хијерархијских односа, као што је структура директоријума у систем датотека.
  • Сортирање података: Можете користити бинарна стабла претраге за ефикасно сортирање података и обављање претраживања, уметања и брисања у логаритамском времену.

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

Закључак

У овом свеобухватном водичу, истражили смо основне концепте бинарних стабала у Ц. Научили смо о њиховој структури, како да убацимо и уклонимо чворове, извршимо обилажење и тражимо елементе у бинарном стаблу.

Надамо се да вам је овај водич пружио солидно разумевање бинарних стабала и начина на који их имплементирате у Ц. Бинарна стабла су разноврсне и моћне структуре података које вам могу помоћи да решите широк спектар проблема у програмирању.

Не заборавите да вежбате и експериментишете са датим примерима да бисте ојачали своје разумевање бинарних стабала у Ц. Срећно на вашем путу учења и развоја софтвера!