Binære trær i C: En komplett nybegynnerveiledning

Informatec Digital » Algoritmer » Binære trær i C: En komplett guide for nybegynnere

Velkommen til denne omfattende guiden om binære trær i C. I denne artikkelen vil vi utforske det grunnleggende om binære trær og hvordan du implementerer dem i programmeringsspråket C Hvis du er nybegynner i programmering eller bare ønsker å forbedre dine C-ferdigheter, er denne veiledningen for deg.

Binære trær er grunnleggende datastrukturer innen informatikk og brukes i en rekke applikasjoner. Å forstå hvordan de fungerer og hvordan du implementerer dem vil hjelpe deg med å løse komplekse problemer mer effektivt og elegant.

Gjennom denne artikkelen skal vi utforske det grunnleggende om binære trær, inkludert strukturen deres, innsetting og sletting av noder, traversering og elementsøk. Vi vil også gi praktiske eksempler i programmeringsspråket C, slik at du kan se hvordan disse konseptene brukes i praksis.

Så la oss komme i gang!

Hva er binære trær?

Binære trær er hierarkiske datastrukturer sammensatt av sammenkoblede noder. Hver node kan ha opptil to underordnede noder: en til venstre og en til høyre. Denne to-grenstrukturen er det som skiller binære trær fra andre datastrukturer.

I et binært tre kalles den første noden rotnoden. Barneknuter kalles barnenoder, og noder uten barn kalles bladnoder. Noder på samme nivå kalles søskennoder.

Fordeler med binære trær

Binære trær gir flere fordeler når det gjelder effektiv datalagring og søking. Noen av de viktigste fordelene inkluderer:

1. Effektivt søkBinære trær gjør at elementer kan søkes under kjøretid raskere enn andre datastrukturer, for eksempel koblede lister. Dette skyldes den hierarkiske strukturen til treet og dets evne til raskt å partisjonere datasettet.
2. Fleksibel innsetting og fjerningBinære trær er svært tilpasningsdyktige til nodeinnsetting og slettingsoperasjoner. I motsetning til statiske datastrukturer som matriser, kan binære trær vokse og endre strukturen deres dynamisk.
3. Representasjon av hierarkiske relasjonerBinære trær er spesielt nyttige for å representere hierarkiske relasjoner mellom elementer. For eksempel, i en filkatalogstruktur, kan hver katalog representeres som en node i treet, med underkataloger og filer som undernoder.

Strukturen til et binært tre

Før vi dykker ned i implementeringen av binære trær i C, er det viktig å forstå deres grunnleggende struktur. Hver node i et binært tre inneholder en verdi og referanser til venstre og høyre underordnede noder, hvis den har noen.

Følgende tabell viser strukturen til en node i et binært tre:

Binær node
Valor
Venstre node
Høyre node

Hver node kan lagre alle typer data, for eksempel heltall, tegn eller mer komplekse strukturer. Rotnoden er startpunktet til treet, og fra den kan vi få tilgang til alle de andre nodene.

Implementering av binære trær i C

Nå som vi har en grunnleggende forståelse av binære trær, er det på tide å implementere dem i programmeringsspråket C. Deretter skal vi se hvordan man deklarerer og bruker en binær trestruktur i C.

Erklære den binære trestrukturen

I C kan vi erklære strukturen til et binært tre ved å bruke en struktur og pekere. Her er den grunnleggende erklæringen om strukturen:

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

I denne strukturen, valor representerer verdien som er lagret i noden, og izquierdo y derecho er pekere til henholdsvis venstre og høyre barnenoder.

Opprette en ny node

For å lage en ny node i det binære treet, må vi allokere minne for noden og sette verdiene. Her er en C-funksjon som lager en ny node:

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

Funksjonen malloc Den brukes til å allokere dynamisk minne til noden. Vi setter deretter nodeverdiene og returnerer den opprettede noden.

Setter inn noder

Nodeinnsetting er en grunnleggende prosess i binære trær. Lar deg legge til nye elementer i treet på riktig posisjon basert på nodeverdien. Nedenfor er en C-funksjon for å sette inn en node i et binært tre:

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

Denne funksjonen mottar en peker til roten av treet og verdien til noden som skal settes inn. Hvis root er null, betyr det at treet er tomt og vi oppretter en ny node ved roten. Ellers sammenligner vi verdien av noden med verdien til roten og bestemmer om vi skal sette inn noden til venstre eller høyre.

Sletter noder

Å slette noder i et binært tre kan være litt mer komplekst. Det avhenger av flere tilfeller, for eksempel om noden som skal slettes har barn eller ikke. Nedenfor er en C-funksjon for å slette en node i et binært tre:

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

I denne funksjonen sjekker vi om verdien til noden er mindre enn, større enn eller lik verdien til gjeldende rot. Avhengig av saken utfører vi følgende handlinger:

• Hvis verdien er mindre, går vi til venstre for treet.
• Hvis verdien er større, går vi til høyre for treet.
• Hvis verdien er lik, finner vi nodens nærmeste etterfølger (den minste noden i høyre undertre) og erstatter den med den nåværende noden. Deretter fjerner vi etterfølgeren fra høyre undertre.

Traverseringer i binære trær

Traverseringer er operasjoner som lar oss besøke alle nodene til et binært tre i en bestemt rekkefølge. Det er tre vanlige typer turer:

Ordensomveisgjennomgang : Besøker først det venstre undertreet, deretter den gjeldende noden og til slutt det høyre undertreet. Her er en C-funksjon som utfører en ordensmessig gjennomgang av et binærtre:

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

Forhåndsbestillingstraversering : Besøker først gjeldende node, deretter venstre undertre og til slutt høyre undertre. Her er en C-funksjon som utfører en forhåndsbestillingstraversering av et binærtre:

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

Etterordre-traversering : Besøker først venstre undertre, deretter høyre undertre og til slutt gjeldende node. Her er en C-funksjon som utfører en etterordre-traversering av et binærtre:

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

Søk etter elementer

Å søke etter elementer i et binært tre lar oss raskt finne en bestemt verdi i datastrukturen. Her er en C-funksjon for å søke etter et element i et binært tre:

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

Denne funksjonen utfører et rekursivt søk i det binære treet. Hvis verdien til gjeldende node er lik den søkte verdien, returneres noden. Ellers søkes det venstre eller høyre undertreet basert på verdien, og prosessen gjentas til verdien er funnet eller en nullnode er nådd.

Eksempler på implementering av binære trær i C

Nå som vi har dekket det grunnleggende om binære trær og hvordan du implementerer dem i C, la oss se på noen praktiske eksempler.

Eksempel 1: Opprette et binært tre

Anta at vi vil lage et binært tre med følgende verdier: 10, 5, 15, 3, 7, 13, 18. Slik kan vi gjøre det i 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;
}

I dette eksemplet lager vi en peker til roten av treet og bruker deretter funksjonen insertarNodo for å legge til verdiene til treet.

Eksempel 2: Traversering av det binære treet i rekkefølge

For å skrive ut verdiene til det binære treet i rekkefølge, kan vi kalle funksjonen inOrden som følger:

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

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

    return 0;
}

Dette eksemplet vil skrive ut verdiene i treet i stigende rekkefølge.

Vanlige spørsmål

1. Hva er forskjellen mellom et binært tre og et binært søketre?

Et binært søketre (BST) er en spesiell type binært tre der elementer er ordnet slik at mindre verdier er til venstre og større verdier er til høyre. Dette muliggjør mer effektivt søk etter elementer sammenlignet med et vanlig binært tre.

2. Kan jeg ha noder med dupliserte verdier i et binært tre?

Ja, det er mulig å ha noder med dupliserte verdier i et binært tre. Avhengig av implementeringen og de spesifikke reglene for det binære treet, kan det imidlertid være forskjellige måter å håndtere dupliserte noder på. Noen implementeringer kan tillate duplikater og lagre dem i hvilken som helst rekkefølge, mens andre kan kreve at dupliserte verdier håndteres spesielt eller forkastes.

3. Hvordan kan jeg fjerne en bestemt node fra et binært tre?

For å fjerne en spesifikk node fra et binært tre, må du følge disse trinnene:

1. Finn noden du vil slette ved å bruke et tresøk.
2. Vurder de forskjellige tilfellene av eliminering:
   • Hvis noden ikke har noen barn, kan du ganske enkelt slette den og frigjøre minnet.
   • Hvis noden bare har ett barn, kan du erstatte noden med dens underordnede.
   • Hvis noden har to barn, må du finne nærmeste etterfølger (den minste noden i høyre undertre) og erstatte verdien til noden som skal slettes med verdien til etterfølgeren. Fjern deretter etterfølgeren fra treet.
3. Justerer lenker og pekere etter behov for å opprettholde riktig trestruktur.

4. Hva er et fullt binært tre?

Et fullt binært tre er en spesiell type binært tre der alle nivåer, unntatt muligens det siste, er fullstendig fylt, og nodene til det siste nivået er plassert så langt til venstre som mulig. Dette betyr at alle noder har to barn, unntatt muligens nodene på siste nivå, som kan ha ett eller ingen barn.

5. Hva er høyden på et binært tre?

Høyden på et binært tre er lengden på den lengste veien fra roten til et blad. Med andre ord er det maksimalt antall kanter mellom roten og ethvert blad i treet. Høyde måles i form av antall nivåer, så et tre med bare én node har en høyde på 0, og et tomt tre har ingen høyde.

6. Når bør jeg bruke et binært tre i programmene mine?

Binære trær er nyttige i en rekke situasjoner. Noen vanlige tilfeller der du kan bruke binære trær inkluderer:

• Effektivt elementoppslag: Hvis du raskt trenger å slå opp elementer i en datastruktur, kan et binært tre gi effektiv tilgang til dataene.
• Representere hierarkiske relasjoner: Binære trær er ideelle for å representere hierarkiske relasjoner, for eksempel katalogstrukturen i en filsystem.
• Datasortering: Du kan bruke binære søketrær til å sortere data effektivt og utføre søk, innsettinger og slettinger i logaritmisk tid.

Husk å evaluere kravene dine og vurdere kompleksiteten til operasjoner på binære trær før du bestemmer deg for å bruke dem i programmene dine.

Konklusjon

I denne omfattende veiledningen har vi utforsket de grunnleggende konseptene for binære trær i C. Vi har lært om strukturen deres, hvordan man setter inn og fjerner noder, utfører traverseringer og søker etter elementer i et binært tre.

Vi håper denne veiledningen har gitt deg en solid forståelse av binære trær og hvordan du implementerer dem i C. Binære trær er allsidige og kraftige datastrukturer som kan hjelpe deg med å løse et bredt spekter av problemer innen programmering.

Husk å øve og eksperimentere med de oppgitte eksemplene for å styrke din forståelse av binære trær i C. Lykke til på din programvarelærings- og utviklingsreise!