Binární stromy v C: Kompletní průvodce pro začátečníky

Informatec Digital » Algoritmy » Binární stromy v C: Kompletní průvodce pro začátečníky

Vítejte v tomto komplexním průvodci binárními stromy v C. V tomto článku prozkoumáme základy binárních stromů a jak je implementovat v programovacím jazyce C Pokud jste začátečník v programování nebo si jen chcete zlepšit své dovednosti v C, je tento průvodce určen právě vám.

Binární stromy jsou základní datové struktury v informatice a používají se v široké škále aplikací. Pochopení toho, jak fungují a jak je implementovat, vám pomůže efektivněji a elegantněji řešit složité problémy.

V tomto článku prozkoumáme základy binárních stromů, včetně jejich struktury, vkládání a mazání uzlů, procházení a vyhledávání prvků. Uvedeme také praktické příklady v programovacím jazyce C , abyste viděli, jak se tyto koncepty uplatňují v praxi.

Pojďme tedy začít!

Co jsou binární stromy?

Binární stromy jsou hierarchické datové struktury složené z propojených uzlů. Každý uzel může mít až dva podřízené uzly: jeden vlevo a jeden vpravo. Tato dvouvětvová struktura je to, co odlišuje binární stromy od jiných datových struktur.

V binárním stromě se první uzel nazývá kořenový uzel. Podřízené uzly se nazývají podřízené uzly a uzly bez potomků se nazývají listové uzly. Uzly na stejné úrovni se nazývají sourozenecké uzly.

Výhody binárních stromů

Binární stromy nabízejí několik výhod, pokud jde o efektivní ukládání a vyhledávání dat. Některé z klíčových výhod zahrnují:

1. Efektivní vyhledáváníBinární stromy umožňují prohledávat prvky za běhu rychleji než jiné datové struktury, jako jsou propojené seznamy. To je způsobeno hierarchickou strukturou stromu a jeho schopností rychle rozdělit soubor dat.
2. Flexibilní vkládání a vyjímáníBinární stromy jsou vysoce adaptabilní pro operace vkládání a mazání uzlů. Na rozdíl od statických datových struktur, jako jsou pole, mohou binární stromy růst a dynamicky měnit svou strukturu.
3. Reprezentace hierarchických vztahůBinární stromy jsou zvláště užitečné pro reprezentaci hierarchických vztahů mezi prvky. Například v adresářové struktuře souborů může být každý adresář reprezentován jako uzel ve stromu s podadresáři a soubory jako jeho podřízené uzly.

Struktura binárního stromu

Než se vrhneme na implementaci binárních stromů v C, je důležité porozumět jejich základní struktuře. Každý uzel v binárním stromu obsahuje hodnotu a odkazy na svůj levý a pravý podřízený uzel, pokud nějaké má.

Následující tabulka ukazuje strukturu uzlu v binárním stromu:

Binární uzel
chrabrost
Levý uzel
Pravý uzel

Každý uzel může ukládat jakýkoli typ dat, jako jsou celá čísla, znaky nebo složitější struktury. Kořenový uzel je výchozím bodem stromu a z něj můžeme přistupovat ke všem ostatním uzlům.

Implementace binárních stromů v C

Nyní, když máme základní znalosti o binárních stromech, je čas je implementovat v programovacím jazyce C. Dále se podíváme, jak deklarovat a používat binární stromovou strukturu v jazyce C.

Deklarace binární stromové struktury

V C můžeme deklarovat strukturu binárního stromu pomocí struktury a ukazatelů. Zde je základní deklarace struktury:

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

V této struktuře, valor představuje hodnotu uloženou v uzlu a izquierdo y derecho jsou ukazatele na levý a pravý podřízený uzel.

Vytvoření nového uzlu

Abychom vytvořili nový uzel v binárním stromu, musíme pro uzel alokovat paměť a nastavit jeho hodnoty. Zde je funkce C, která vytvoří nový uzel:

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

Funkce malloc Používá se k přidělení dynamické paměti uzlu. Poté nastavíme hodnoty uzlu a vrátíme vytvořený uzel.

Vkládání uzlů

Vkládání uzlů je základní proces v binárních stromech. Umožňuje přidat nové prvky do stromu na správnou pozici na základě hodnoty uzlu. Níže je funkce C pro vložení uzlu do binárního stromu:

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

Tato funkce obdrží ukazatel na kořen stromu a hodnotu uzlu, který má být vložen. Pokud je root null, znamená to, že strom je prázdný a v kořeni vytvoříme nový uzel. V opačném případě porovnáme hodnotu uzlu s hodnotou kořene a rozhodneme se, zda vložíme uzel vlevo nebo vpravo.

Mazání uzlů

Odstraňování uzlů v binárním stromu může být trochu složitější. Záleží na několika případech, například zda má uzel, který má být odstraněn, potomky nebo ne. Níže je funkce C pro odstranění uzlu v binárním stromu:

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

V této funkci zkontrolujeme, zda je hodnota uzlu menší, větší nebo rovna hodnotě aktuálního kořene. V závislosti na případu provádíme následující akce:

• Pokud je hodnota menší, jdeme nalevo od stromu.
• Pokud je hodnota větší, jdeme napravo od stromu.
• Pokud je hodnota rovna, najdeme nejbližšího následníka uzlu (nejmenší uzel v pravém podstromu) a nahradíme jej aktuálním uzlem. Poté odstraníme následníka z pravého podstromu.

Traverzy v binárních stromech

Traversals jsou operace, které nám umožňují navštívit všechny uzly binárního stromu v určitém pořadí. Existují tři běžné typy zájezdů:

Procházení v pořadí : Nejprve navštíví levý podstrom, poté aktuální uzel a nakonec pravý podstrom. Zde je funkce v jazyce C, která provádí procházení binárního stromu v pořadí:

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

Předběžné procházení : Nejprve navštíví aktuální uzel, poté levý podstrom a nakonec pravý podstrom. Zde je funkce v jazyce C, která provádí předběžné procházení binárního stromu:

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

Procházení po pořadí : Nejprve navštíví levý podstrom, poté pravý podstrom a nakonec aktuální uzel. Zde je funkce v jazyce C, která provádí procházení binárního stromu po pořadí:

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

Hledejte prvky

Vyhledávání prvků v binárním stromu nám umožňuje rychle najít konkrétní hodnotu v rámci datové struktury. Zde je funkce C pro vyhledání prvku v binárním stromu:

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

Tato funkce provádí rekurzivní vyhledávání v binárním stromu. Pokud je hodnota aktuálního uzlu rovna hledané hodnotě, je uzel vrácen. V opačném případě je levý nebo pravý podstrom prohledán na základě hodnoty a proces se opakuje, dokud není hodnota nalezena nebo dokud není dosaženo nulového uzlu.

Příklady implementace binárních stromů v C

Nyní, když jsme probrali základy binárních stromů a jak je implementovat v C, podívejme se na praktické příklady.

Příklad 1: Vytvoření binárního stromu

Předpokládejme, že chceme vytvořit binární strom s následujícími hodnotami: 10, 5, 15, 3, 7, 13, 18. Zde je návod, jak to udělat v 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;
}

V tomto příkladu vytvoříme ukazatel na kořen stromu a poté použijeme funkci insertarNodo přidat hodnoty do stromu.

Příklad 2: Průběh binárního stromu v pořadí

Chcete-li vytisknout hodnoty binárního stromu v pořadí, můžeme zavolat funkci inOrden takto:

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

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

    return 0;
}

Tento příklad vytiskne hodnoty ve stromu ve vzestupném pořadí.

Preguntas frecuentes

1. Jaký je rozdíl mezi binárním stromem a binárním vyhledávacím stromem?

Binární vyhledávací strom (BST) je speciální typ binárního stromu, ve kterém jsou prvky uspořádány tak, že menší hodnoty jsou vlevo a větší hodnoty jsou vpravo. To umožňuje efektivnější vyhledávání prvků ve srovnání s běžným binárním stromem.

2. Mohu mít uzly s duplicitními hodnotami v binárním stromu?

Ano, je možné mít uzly s duplicitními hodnotami v binárním stromu. V závislosti na implementaci a konkrétních pravidlech binárního stromu však mohou existovat různé způsoby, jak se vypořádat s duplicitními uzly. Některé implementace mohou povolit duplikáty a ukládat je v libovolném pořadí, zatímco jiné mohou vyžadovat, aby se s duplicitními hodnotami zacházelo speciálně nebo aby byly odstraněny.

3. Jak mohu odstranit konkrétní uzel z binárního stromu?

Chcete-li odebrat konkrétní uzel z binárního stromu, musíte provést následující kroky:

1. Najděte uzel, který chcete odstranit, pomocí stromového vyhledávání.
2. Zvažte různé případy eliminace:
   • Pokud uzel nemá žádné potomky, můžete jej jednoduše smazat a uvolnit jeho paměť.
   • Pokud má uzel pouze jednoho potomka, můžete uzel nahradit jeho potomkem.
   • Pokud má uzel dva potomky, musíte najít nejbližšího následníka (nejmenší uzel v pravém podstromu) a nahradit hodnotu uzlu, který má být odstraněn, hodnotou následníka. Poté ze stromu odeberte nástupce.
3. Upraví odkazy a ukazatele podle potřeby, aby byla zachována správná stromová struktura.

4. Co je úplný binární strom?

Úplný binární strom je speciální typ binárního stromu, ve kterém jsou všechny úrovně, možná kromě poslední, zcela vyplněny a uzly poslední úrovně jsou umístěny co nejvíce vlevo. To znamená, že všechny uzly mají dva potomky, možná kromě uzlů na poslední úrovni, které mohou mít jednoho nebo žádného potomka.

5. Jakou výšku má binární strom?

Výška binárního stromu je délka nejdelší cesty od kořene k listu. Jinými slovy, je to maximální počet hran mezi kořenem a libovolným listem ve stromu. Výška se měří jako počet úrovní, takže strom s pouze jedním uzlem má výšku 0 a prázdný strom nemá výšku.

6. Kdy bych měl ve svých programech používat binární strom?

Binární stromy jsou užitečné v různých situacích. Některé běžné případy, kdy byste mohli použít binární stromy, zahrnují:

• Efektivní vyhledávání prvků: Pokud potřebujete rychle vyhledat prvky v datové struktuře, binární strom může poskytnout efektivní přístup k datům.
• Reprezentace hierarchických vztahů: Binární stromy jsou ideální pro reprezentaci hierarchických vztahů, jako je struktura adresářů v souborový systém.
• Třídění dat: Binární vyhledávací stromy můžete použít k efektivnímu třídění dat a provádění vyhledávání, vkládání a mazání v logaritmickém čase.

Než se rozhodnete je použít ve svých programech, nezapomeňte vyhodnotit své požadavky a zvážit složitost operací s binárními stromy.

Závěr

V této obsáhlé příručce jsme prozkoumali základní koncepty binárních stromů v C. Dozvěděli jsme se o jejich struktuře, jak vkládat a odstraňovat uzly, provádět procházení a hledat prvky v binárním stromu.

Doufáme, že vám tato příručka poskytla solidní znalosti o binárních stromech a jejich implementaci v jazyce C. Binární stromy jsou všestranné a výkonné datové struktury, které vám mohou pomoci vyřešit širokou škálu problémů v programování.

Nezapomeňte procvičovat a experimentovat s poskytnutými příklady, abyste posílili své porozumění binárním stromům v C. Hodně štěstí na vaší cestě učení a vývoje softwaru!