Binære træer i C: En komplet begyndervejledning

Informatec Digital » Algoritmer » Binære træer i C: En komplet guide til begyndere

Velkommen til denne omfattende guide om binære træer i C. I denne artikel vil vi udforske det grundlæggende i binære træer, og hvordan du implementerer dem i programmeringssproget C. Hvis du er nybegynder i programmering eller blot ønsker at forbedre dine C-færdigheder, er denne guide noget for dig.

Binære træer er grundlæggende datastrukturer inden for datalogi og bruges i en bred vifte af applikationer. Forståelse af, hvordan de fungerer, og hvordan man implementerer dem, vil hjælpe dig med at løse komplekse problemer mere effektivt og elegant.

Igennem denne artikel vil vi udforske det grundlæggende i binære træer, herunder deres struktur, nodeindsættelse og -sletning, gennemgang og elementsøgning. Vi vil også give praktiske eksempler i programmeringssproget C, så du kan se, hvordan disse koncepter anvendes i praksis.

Så lad os komme i gang!

Hvad er binære træer?

Binære træer er hierarkiske datastrukturer sammensat af indbyrdes forbundne noder. Hver node kan have op til to underordnede noder: en til venstre og en til højre. Denne to-grenede struktur er det, der adskiller binære træer fra andre datastrukturer.

I et binært træ kaldes den første node rodknuden. Børneknuder kaldes børneknuder, og knuder uden børn kaldes bladknuder. Noder på samme niveau kaldes søskendenoder.

Fordele ved binære træer

Binære træer tilbyder flere fordele i form af effektiv datalagring og søgning. Nogle af de vigtigste fordele inkluderer:

1. Effektiv søgningBinære træer gør det muligt at søge i elementer under kørsel hurtigere end andre datastrukturer, såsom sammenkædede lister. Dette skyldes træets hierarkiske struktur og dets evne til hurtigt at opdele datasættet.
2. Fleksibel isætning og fjernelseBinære træer er meget tilpasningsdygtige til nodeindsættelse og sletningsoperationer. I modsætning til statiske datastrukturer såsom arrays, kan binære træer vokse og ændre deres struktur dynamisk.
3. Repræsentation af hierarkiske relationerBinære træer er især nyttige til at repræsentere hierarkiske relationer mellem elementer. For eksempel, i en filmappestruktur kan hver mappe repræsenteres som en node i træet med undermapper og filer som dens underordnede noder.

Struktur af et binært træ

Før vi dykker ned i implementeringen af ​​binære træer i C, er det vigtigt at forstå deres grundlæggende struktur. Hver node i et binært træ indeholder en værdi og referencer til dens venstre og højre underordnede noder, hvis den har nogen.

Følgende tabel viser strukturen af ​​en node i et binært træ:

Binær knude
værdi
Venstre knudepunkt
Højre knudepunkt

Hver node kan gemme enhver type data, såsom heltal, tegn eller mere komplekse strukturer. Rodknuden er udgangspunktet for træet, og fra den kan vi få adgang til alle de andre knudepunkter.

Implementering af binære træer i C

Nu hvor vi har en grundlæggende forståelse af binære træer, er det tid til at implementere dem i programmeringssproget C. Dernæst vil vi se på, hvordan man deklarerer og bruger en binær træstruktur i C.

Erklæring af den binære træstruktur

I C kan vi erklære strukturen af ​​et binært træ ved hjælp af en struktur og pointere. Her er den grundlæggende erklæring om strukturen:

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

I denne struktur, valor repræsenterer værdien gemt i noden, og izquierdo y derecho er pointere til henholdsvis venstre og højre underordnede knudepunkter.

Oprettelse af en ny node

For at oprette en ny node i det binære træ, skal vi allokere hukommelse til noden og indstille dens værdier. Her er en C-funktion, der opretter 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;
}

Funktionen malloc Det bruges til at allokere dynamisk hukommelse til noden. Vi indstiller derefter nodeværdierne og returnerer den oprettede node.

Indsættelse af noder

Node-indsættelse er en grundlæggende proces i binære træer. Giver dig mulighed for at tilføje nye elementer til træet på den korrekte position baseret på nodeværdien. Nedenfor er en C-funktion til at indsætte en node i et binært træ:

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 funktion modtager en pointer til roden af ​​træet og værdien af ​​den node, der skal indsættes. Hvis root er nul, betyder det, at træet er tomt, og vi opretter en ny node ved roden. Ellers sammenligner vi værdien af ​​noden med værdien af ​​roden og beslutter, om vi skal indsætte noden til venstre eller højre.

Sletning af noder

Sletning af noder i et binært træ kan være lidt mere komplekst. Det afhænger af flere tilfælde, såsom om den node, der skal slettes, har børn eller ej. Nedenfor er en C-funktion til at slette en node i et binært træ:

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 funktion kontrollerer vi, om værdien af ​​noden er mindre end, større end eller lig med værdien af ​​den aktuelle rod. Afhængigt af sagen udfører vi følgende handlinger:

• Hvis værdien er mindre, går vi til venstre for træet.
• Hvis værdien er større, går vi til højre for træet.
• Hvis værdien er lig, finder vi nodens nærmeste efterfølger (den mindste node i højre undertræ) og erstatter den med den aktuelle node. Så fjerner vi efterfølgeren fra det højre undertræ.

Traverseringer i binære træer

Traversaler er operationer, der giver os mulighed for at besøge alle noder i et binært træ i en bestemt rækkefølge. Der er tre almindelige typer ture:

Ordensom gennemgang : Besøger først det venstre undertræ, derefter den aktuelle node og til sidst det højre undertræ. Her er en C-funktion, der udfører en ordensom gennemgang af et binært træ:

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

Forudbestillingstraversal : Besøger først den aktuelle node, derefter det venstre undertræ og til sidst det højre undertræ. Her er en C-funktion, der udfører en forudbestillingstraversal af et binært træ:

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

Post-ordre traversal : Besøger først det venstre undertræ, derefter det højre undertræ og til sidst den aktuelle node. Her er en C-funktion, der udfører en post-ordre traversal af et binært træ:

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

Søg efter elementer

Søgning efter elementer i et binært træ giver os mulighed for hurtigt at finde en bestemt værdi i datastrukturen. Her er en C-funktion til at søge efter et element i et binært træ:

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 funktion udfører en rekursiv søgning i det binære træ. Hvis værdien af ​​den aktuelle node er lig med den søgte værdi, returneres noden. Ellers søges det venstre eller højre undertræ baseret på værdien, og processen gentages, indtil værdien er fundet, eller en nulknude er nået.

Eksempler på implementering af binære træer i C

Nu hvor vi har dækket det grundlæggende i binære træer og hvordan man implementerer dem i C, lad os se på nogle praktiske eksempler.

Eksempel 1: Oprettelse af et binært træ

Antag, at vi vil skabe et binært træ med følgende værdier: 10, 5, 15, 3, 7, 13, 18. Her er hvordan vi kan gø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 eksempel opretter vi en pointer til roden af ​​træet og bruger derefter funktionen insertarNodo for at tilføje værdierne til træet.

Eksempel 2: Gennemgang i rækkefølge af det binære træ

For at udskrive værdierne af det binære træ i rækkefølge kan vi kalde funktionen inOrden som følger:

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

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

    return 0;
}

Dette eksempel vil udskrive værdierne i træet i stigende rækkefølge.

Ofte stillede spørgsmål

1. Hvad er forskellen mellem et binært træ og et binært søgetræ?

Et binært søgetræ (BST) er en speciel type binært træ, hvor elementer er arrangeret således, at mindre værdier er til venstre og større værdier er til højre. Dette giver mulighed for mere effektiv søgning af elementer sammenlignet med et almindeligt binært træ.

2. Kan jeg have noder med duplikerede værdier i et binært træ?

Ja, det er muligt at have noder med duplikerede værdier i et binært træ. Men afhængigt af implementeringen og de specifikke regler for det binære træ, kan der være forskellige måder at håndtere duplikerede noder på. Nogle implementeringer kan tillade dubletter og gemme dem i enhver rækkefølge, mens andre kan kræve, at duplikerede værdier håndteres specielt eller kasseres.

3. Hvordan kan jeg fjerne en specifik node fra et binært træ?

For at fjerne en specifik node fra et binært træ skal du følge disse trin:

1. Find den node, du vil slette, ved hjælp af en træsøgning.
2. Overvej de forskellige tilfælde af eliminering:
   • Hvis noden ikke har nogen børn, kan du blot slette den og frigøre dens hukommelse.
   • Hvis noden kun har ét underordnet, kan du erstatte knudepunktet med dets underordnede.
   • Hvis noden har to børn, skal du finde den nærmeste efterfølger (den mindste node i højre undertræ) og erstatte værdien af ​​den node, der skal slettes, med værdien af ​​efterfølgeren. Fjern derefter efterfølgeren fra træet.
3. Justerer links og pointere efter behov for at opretholde den korrekte træstruktur.

4. Hvad er et fuldt binært træ?

Et fuldt binært træ er en speciel type binært træ, hvor alle niveauer, undtagen muligvis det sidste, er fuldstændigt udfyldt, og noderne på det sidste niveau er placeret så langt til venstre som muligt. Det betyder, at alle noder har to børn, undtagen muligvis noderne på sidste niveau, som kan have et eller ingen børn.

5. Hvad er højden af ​​et binært træ?

Højden af ​​et binært træ er længden af ​​den længste vej fra roden til et blad. Det er med andre ord det maksimale antal kanter mellem roden og ethvert blad i træet. Højde måles i antal niveauer, så et træ med kun én knude har en højde på 0, og et tomt træ har ingen højde.

6. Hvornår skal jeg bruge et binært træ i mine programmer?

Binære træer er nyttige i en række forskellige situationer. Nogle almindelige tilfælde, hvor du måske bruger binære træer, omfatter:

• Effektivt elementopslag: Hvis du hurtigt skal slå elementer op i en datastruktur, kan et binært træ give effektiv adgang til dataene.
• Repræsentation af hierarkiske relationer: Binære træer er ideelle til at repræsentere hierarkiske relationer, såsom mappestrukturen i en filsystem.
• Datasortering: Du kan bruge binære søgetræer til effektivt at sortere data og udføre søgninger, indsættelser og sletninger i logaritmisk tid.

Husk at evaluere dine krav og overveje kompleksiteten af ​​operationer på binære træer, før du beslutter dig for at bruge dem i dine programmer.

Konklusion

I denne omfattende guide har vi udforsket de grundlæggende begreber for binære træer i C. Vi har lært om deres struktur, hvordan man indsætter og fjerner noder, udfører traverseringer og søger efter elementer i et binært træ.

Vi håber, at denne guide har givet dig en solid forståelse af binære træer og hvordan du implementerer dem i C. Binære træer er alsidige og kraftfulde datastrukturer, der kan hjælpe dig med at løse en lang række problemer inden for programmering.

Husk at øve og eksperimentere med de medfølgende eksempler for at styrke din forståelse af binære træer i C. Held og lykke med din softwareindlærings- og udviklingsrejse!