|

Structuri de Date Arborescente Implementate Dinamic – Arbori 12


1. Obiectivele lecției:

  • Să înțeleagă conceptul de arbore și proprietățile acestuia.
  • Să învețe cum să implementeze un arbore binar folosind alocarea dinamică a memoriei.
  • Să implementeze operații comune pe arbori: inserare, traversare (în ordine, preordine, postordine) și căutare.

2. Ce este un arbore?

  1. Definiție:
    Un arbore este o structură de date non-liniară care conține noduri organizate ierarhic. Fiecare nod poate avea copii, iar primul nod este numit rădăcină (root).
  2. Proprietăți ale arborilor:
    • Un arbore are un singur nod rădăcină.
    • Fiecare nod are un părinte, cu excepția rădăcinii.
    • Nodurile fără copii se numesc frunze (leaves).
    • Un arbore poate avea subarbori.
  3. Tipuri de arbori:
    • Arbore binar: Fiecare nod poate avea cel mult doi copii.
    • Arbore binar de căutare (BST): Valorile din subarborele stâng sunt mai mici decât rădăcina, iar cele din subarborele drept sunt mai mari.

3. Avantaje și dezavantaje

AvantajeDezavantaje
Eficient pentru căutări rapide în structuri mari (BST).Implementarea și gestionarea sunt mai complexe.
Structură flexibilă pentru date ierarhice.Consumul de memorie crește cu dimensiunea arborelui.

4. Structura unui nod

  1. Structura unui nod pentru un arbore binar:

struct Nod {

    int valoare;       // Informația stocată

    Nod* stanga;       // Pointer către subarborele stâng

    Nod* dreapta;      // Pointer către subarborele drept

};

  1. Pointerul către rădăcina arborelui:

Nod* radacina = nullptr;


5. Operații comune pe arbori binari


1. Crearea unui nod

Nod* creeazaNod(int valoare) {

    Nod* nod = new Nod();

    nod->valoare = valoare;

    nod->stanga = nullptr;

    nod->dreapta = nullptr;

    return nod;

}


2. Inserarea unui nod într-un arbore binar de căutare (BST)

  1. Funcția de inserare:

Nod* insereazaNod(Nod* radacina, int valoare) {

    if (radacina == nullptr) {

        return creeazaNod(valoare);

    }

    if (valoare < radacina->valoare) {

        radacina->stanga = insereazaNod(radacina->stanga, valoare);

    } else if (valoare > radacina->valoare) {

        radacina->dreapta = insereazaNod(radacina->dreapta, valoare);

    }

    return radacina;

}


3. Traversări ale arborelui

  1. Traversare în ordine (in-order):
    Vizitează nodurile în ordinea: stânga → rădăcină → dreapta.

void traversareInOrdine(Nod* radacina) {

    if (radacina == nullptr) return;

    traversareInOrdine(radacina->stanga);

    cout << radacina->valoare << ” „;

    traversareInOrdine(radacina->dreapta);

}

  1. Traversare preordine (pre-order):
    Vizitează nodurile în ordinea: rădăcină → stânga → dreapta.

void traversarePreOrdine(Nod* radacina) {

    if (radacina == nullptr) return;

    cout << radacina->valoare << ” „;

    traversarePreOrdine(radacina->stanga);

    traversarePreOrdine(radacina->dreapta);

}

  1. Traversare postordine (post-order):
    Vizitează nodurile în ordinea: stânga → dreapta → rădăcină.

void traversarePostOrdine(Nod* radacina) {

    if (radacina == nullptr) return;

    traversarePostOrdine(radacina->stanga);

    traversarePostOrdine(radacina->dreapta);

    cout << radacina->valoare << ” „;

}


4. Căutarea unui element

  1. Funcția de căutare:

bool cautaValoare(Nod* radacina, int valoare) {

    if (radacina == nullptr) {

        return false;

    }

    if (valoare == radacina->valoare) {

        return true;

    } else if (valoare < radacina->valoare) {

        return cautaValoare(radacina->stanga, valoare);

    } else {

        return cautaValoare(radacina->dreapta, valoare);

    }

}


5. Exemplu complet

#include <iostream>

using namespace std;

struct Nod {

    int valoare;

    Nod* stanga;

    Nod* dreapta;

};

Nod* creeazaNod(int valoare) {

    Nod* nod = new Nod();

    nod->valoare = valoare;

    nod->stanga = nullptr;

    nod->dreapta = nullptr;

    return nod;

}

Nod* insereazaNod(Nod* radacina, int valoare) {

    if (radacina == nullptr) {

        return creeazaNod(valoare);

    }

    if (valoare < radacina->valoare) {

        radacina->stanga = insereazaNod(radacina->stanga, valoare);

    } else if (valoare > radacina->valoare) {

        radacina->dreapta = insereazaNod(radacina->dreapta, valoare);

    }

    return radacina;

}

void traversareInOrdine(Nod* radacina) {

    if (radacina == nullptr) return;

    traversareInOrdine(radacina->stanga);

    cout << radacina->valoare << ” „;

    traversareInOrdine(radacina->dreapta);

}

bool cautaValoare(Nod* radacina, int valoare) {

    if (radacina == nullptr) {

        return false;

    }

    if (valoare == radacina->valoare) {

        return true;

    } else if (valoare < radacina->valoare) {

        return cautaValoare(radacina->stanga, valoare);

    } else {

        return cautaValoare(radacina->dreapta, valoare);

    }

}

int main() {

    Nod* radacina = nullptr;

    radacina = insereazaNod(radacina, 50);

    insereazaNod(radacina, 30);

    insereazaNod(radacina, 70);

    insereazaNod(radacina, 20);

    insereazaNod(radacina, 40);

    insereazaNod(radacina, 60);

    insereazaNod(radacina, 80);

    cout << „Traversare în ordine: „;

    traversareInOrdine(radacina);

    cout << endl;

    cout << „Căutare valoare 40: ” << (cautaValoare(radacina, 40) ? „Găsită” : „Negăsită”) << endl;

    cout << „Căutare valoare 25: ” << (cautaValoare(radacina, 25) ? „Găsită” : „Negăsită”) << endl;

    return 0;

}


6. Activități practice pentru elevi

  1. Implementați o funcție care determină numărul de noduri dintr-un arbore.
  2. Realizați o funcție care calculează înălțimea unui arbore.
  3. Scrieți un program care determină dacă un arbore este arbore binar de căutare.

7. Scheme logice

  1. Inserare:
    • Verifică dacă nodul curent este gol -> Creează un nou nod -> Compară valoarea și inserează în stânga sau dreapta.
  2. Traversare:
    • Utilizează recursivitate pentru a parcurge nodurile în ordinea specificată.
  3. Căutare:
    • Compară valoarea căutată cu nodul curent -> Explorează subarborele corespunzător.

8. Concluzie

  • Arborii sunt structuri de date esențiale pentru gestionarea informațiilor ierarhice și pentru căutări rapide.
  • Implementarea arborilor binari necesită înțelegerea recursivității.
  • Practica ajută la stăpânirea conceptelor și implementării eficiente.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *