Binära träd i C: En komplett nybörjarguide

Informatec Digital » Algoritmer » Binära träd i C: En komplett nybörjarguide

Välkommen till den här omfattande guiden om binära träd i C. I den här artikeln kommer vi att utforska grunderna i binära träd och hur du implementerar dem i programmeringsspråket C Om du är nybörjare inom programmering eller bara vill förbättra dina C-färdigheter, är den här guiden för dig.

mycket binära träd De är grundläggande datastrukturer inom datavetenskap och används i ett brett spektrum av tillämpningar. Att förstå hur de fungerar och hur man implementerar dem hjälper dig att lösa komplexa problem mer effektivt och elegant.

Genom hela den här artikeln kommer vi att utforska grunderna för binära träd, inklusive deras struktur, infogning och borttagning av noder, genomgångar och sökning efter element. Vi kommer också att ge dig praktiska exempel i språk C så att du kan se hur dessa begrepp tillämpas i praktiken.

Så låt oss börja!

Vad är binära träd?

Binära träd är hierarkiska datastrukturer sammansatta av sammankopplade noder. Varje nod kan ha upp till två underordnade noder: en till vänster och en till höger. Denna tvågrenade struktur är det som skiljer binära träd från andra datastrukturer.

I ett binärt träd kallas den första noden rotnoden. Barnnoder kallas barnnoder, och noder utan barn kallas lövnoder. Noder på samma nivå kallas syskonnoder.

Fördelar med binära träd

Binära träd erbjuder flera fördelar när det gäller effektiv datalagring och sökning. Några av de viktigaste fördelarna inkluderar:

1. Effektiv sökningBinära träd gör att element kan sökas under körning snabbare än andra datastrukturer, såsom länkade listor. Detta beror på trädets hierarkiska struktur och dess förmåga att snabbt partitionera datamängden.
2. Flexibel insättning och borttagningBinära träd är mycket anpassningsbara för nodinfogning och raderingsoperationer. Till skillnad från statiska datastrukturer som arrayer kan binära träd växa och förändra sin struktur dynamiskt.
3. Representation av hierarkiska relationerBinära träd är särskilt användbara för att representera hierarkiska relationer mellan element. Till exempel, i en filkatalogstruktur kan varje katalog representeras som en nod i trädet, med underkataloger och filer som dess undernoder.

Struktur av ett binärt träd

Innan vi dyker in i implementeringen av binära träd i C är det viktigt att förstå deras grundläggande struktur. Varje nod i ett binärt träd innehåller ett värde och referenser till dess vänstra och högra underordnade noder, om den har några.

Följande tabell visar strukturen för en nod i ett binärt träd:

Binär nod
valor
Vänster nod
Höger nod

Varje nod kan lagra vilken typ av data som helst, såsom heltal, tecken eller mer komplexa strukturer. Rotnoden är startpunkten för trädet, och från den kan vi komma åt alla andra noder.

Implementera binära träd i C

Nu när vi har en grundläggande förståelse för binära träd är det dags att implementera dem i C programmeringsspråk. Därefter kommer vi att se hur man deklarerar och använder en binär trädstruktur i C.

Deklarerar den binära trädstrukturen

I C kan vi deklarera strukturen för ett binärt träd med hjälp av en struktur och pekare. Här är den grundläggande deklarationen av strukturen:

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

I denna struktur, valor representerar värdet som är lagrat i noden, och izquierdo y derecho är pekare till vänster respektive höger barnnod.

Skapar en ny nod

För att skapa en ny nod i det binära trädet måste vi allokera minne för noden och ställa in dess värden. Här är en C-funktion som skapar en ny nod:

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 Den används för att allokera dynamiskt minne till noden. Vi ställer sedan in nodvärdena och returnerar den skapade noden.

Infoga noder

Nodinfogning är en grundläggande process i binära träd. Låter dig lägga till nya element i trädet på rätt position baserat på nodvärdet. Nedan finns en C-funktion för att infoga en nod i ett binärt träd:

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

Denna funktion tar emot en pekare till trädets rot och värdet på noden som ska infogas. Om root är null betyder det att trädet är tomt och vi skapar en ny nod vid roten. Annars jämför vi nodens värde med rotens värde och bestämmer om vi ska infoga noden till vänster eller höger.

Tar bort noder

Att ta bort noder i ett binärt träd kan vara lite mer komplicerat. Det beror på flera fall, till exempel om noden som ska raderas har barn eller inte. Nedan finns en C-funktion för att ta bort en nod i ett binärt träd:

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 den här funktionen kontrollerar vi om nodens värde är mindre än, större än eller lika med värdet på den aktuella roten. Beroende på ärendet utför vi följande åtgärder:

• Om värdet är mindre går vi till vänster om trädet.
• Om värdet är större går vi till höger om trädet.
• Om värdet är lika hittar vi nodens närmaste efterföljare (den minsta noden i det högra underträdet) och ersätter den med den aktuella noden. Sedan tar vi bort efterföljaren från det högra underträdet.

Traverseringar i binära träd

Traverser är operationer som gör att vi kan besöka alla noder i ett binärt träd i en viss ordning. Det finns tre vanliga typer av turer:

Traversering i ordning: Besök det vänstra underträdet först, sedan den aktuella noden och slutligen det högra underträdet. Här är en C-funktion som utför en ordningsgenomgång av ett binärt träd:

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

Förbeställ turné: Besök den aktuella noden först, sedan det vänstra underträdet och slutligen det högra underträdet. Här är en C-funktion som utför en förbeställningsgenomgång av ett binärt träd:

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

Genomgång efter order: Besök först det vänstra underträdet, sedan det högra underträdet och slutligen den aktuella noden. Här är en C-funktion som utför en postorder-traversering av ett binärt träd:

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

Sök efter element

Genom att söka efter element i ett binärt träd kan vi snabbt hitta ett specifikt värde inom datastrukturen. Här är en C-funktion för att söka efter ett element i ett binärt träd:

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

Denna funktion utför en rekursiv sökning i det binära trädet. Om värdet på den aktuella noden är lika med det sökta värdet returneras noden. Annars söks det vänstra eller högra underträdet baserat på värdet och processen upprepas tills värdet hittas eller en nollnod nås.

Exempel på implementering av binära träd i C

Nu när vi har täckt grunderna för binära träd och hur man implementerar dem i C, låt oss titta på några praktiska exempel.

Exempel 1: Skapa ett binärt träd

Anta att vi vill skapa ett binärt träd med följande värden: 10, 5, 15, 3, 7, 13, 18. Så här kan vi göra 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 det här exemplet skapar vi en pekare till trädets rot och använder sedan funktionen insertarNodo för att lägga till värdena i trädet.

Exempel 2: Genomgång av det binära trädet i ordning

För att skriva ut värdena för det binära trädet i ordning kan vi anropa funktionen inOrden som följer:

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

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

    return 0;
}

Detta exempel kommer att skriva ut värdena i trädet i stigande ordning.

Vanliga frågor

1. Vad är skillnaden mellan ett binärt träd och ett binärt sökträd?

Ett binärt sökträd (BST) är en speciell typ av binärt träd där element är ordnade så att mindre värden finns till vänster och större värden till höger. Detta möjliggör mer effektiv sökning av element jämfört med ett vanligt binärt träd.

2. Kan jag ha noder med dubbla värden i ett binärt träd?

Ja, det är möjligt att ha noder med dubbla värden i ett binärt träd. Men beroende på implementeringen och de specifika reglerna för det binära trädet kan det finnas olika sätt att hantera dubbletter av noder. Vissa implementeringar kan tillåta dubbletter och lagra dem i valfri ordning, medan andra kan kräva att dubbletter av värden hanteras speciellt eller kasseras.

3. Hur kan jag ta bort en specifik nod från ett binärt träd?

För att ta bort en specifik nod från ett binärt träd måste du följa dessa steg:

1. Hitta noden du vill ta bort med en trädsökning.
2. Tänk på de olika fallen av eliminering:
   • Om noden inte har några barn kan du helt enkelt ta bort den och frigöra dess minne.
   • Om noden bara har ett barn kan du ersätta noden med dess underordnade.
   • Om noden har två barn måste du hitta närmaste efterföljare (den minsta noden i det högra underträdet) och ersätta värdet på noden som ska raderas med värdet på efterträdaren. Ta sedan bort efterträdaren från trädet.
3. Justerar länkar och pekare efter behov för att bibehålla rätt trädstruktur.

4. Vad är ett helt binärt träd?

Ett helt binärt träd är en speciell typ av binärt träd där alla nivåer, utom möjligen den sista, är helt fyllda, och noderna på den sista nivån är placerade så långt till vänster som möjligt. Det betyder att alla noder har två barn, utom möjligen noderna på den sista nivån, som kan ha ett eller inga barn.

5. Vad är höjden på ett binärt träd?

Höjden på ett binärt träd är längden på den längsta vägen från roten till ett löv. Det är med andra ord det maximala antalet kanter mellan roten och eventuellt löv i trädet. Höjd mäts i termer av antal nivåer, så ett träd med bara en nod har höjden 0 och ett tomt träd har ingen höjd.

6. När ska jag använda ett binärt träd i mina program?

Binära träd är användbara i en mängd olika situationer. Några vanliga fall där du kan använda binära träd inkluderar:

• Effektiv elementsökning: Om du snabbt behöver slå upp element i en datastruktur kan ett binärt träd ge effektiv åtkomst till data.
• Representera hierarkiska relationer: Binära träd är idealiska för att representera hierarkiska relationer, såsom katalogstrukturen i en filsystem.
• Datasortering: Du kan använda binära sökträd för att effektivt sortera data och utföra sökningar, infogningar och raderingar i logaritmisk tid.

Kom ihåg att utvärdera dina krav och överväga komplexiteten i operationer på binära träd innan du bestämmer dig för att använda dem i dina program.

Slutsats

I den här omfattande guiden har vi utforskat de grundläggande begreppen för binära träd i C. Vi har lärt oss om deras struktur, hur man infogar och tar bort noder, utför traverseringar och söker efter element i ett binärt träd.

Vi hoppas att den här guiden har gett dig en gedigen förståelse för binära träd och hur du implementerar dem i C. Binära träd är mångsidiga och kraftfulla datastrukturer som kan hjälpa dig att lösa ett brett spektrum av problem inom programmering.

Kom ihåg att öva och experimentera med de medföljande exemplen för att stärka din förståelse av binära träd i C. Lycka till på din inlärnings- och utvecklingsresa för programvara!