Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

Cerința

Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.

Date de intrare

Fișierul de intrare bst.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire bst.out va conține pe prima linie, separate prin spațiu, cele n numere din șir, ordonate crescător.

Restricții și precizări

1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un BST, apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
Se știe că există cazuri când un BST poate avea multe nivele și în consecință complexitatea sortării să fie chiar O(n x n). Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu log₂n.

Exemplu

bst.in

10
20 7 13 200 15 100 25 3 17 39

bst.out

3 7 13 15 17 20 25 39 100 200

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema bst:

#include <bits/stdc++.h>
using namespace std;

struct BST
{
    int val, fr;
    BST *st, *dr;

    BST(int v)
    {
        val = v; fr = 1;
        st = dr = NULL;
    }
};
BST *rad;

ifstream  fin("bst.in");
ofstream fout("bst.out");

void Inserare(int x)
{
    /// arborele este vid
    if (rad == NULL)
    {
        rad = new BST(x);
        return;
    }

    BST *p, *q;
    p = q = rad;
    while (p != NULL)
    {
        if (p->val == x)
        {
            p->fr++;
            return;
        }
        q = p;
        if (p->val < x) p = p->dr;
        else p = p->st;
    }
    p = new BST(x);
    if (q->val > x) q->st = p;
    else q->dr = p;
}

void CreareBST()
{
    int n, x;
    fin >> n;
    while (n--)
    {
        fin >> x;
        Inserare(x);
    }
}

void Inord(BST *p)
{
    if (p != NULL)
    {
        Inord(p->st);
        int cnt = p->fr;
        while (cnt--)
            fout << p->val << " ";
        Inord(p->dr);
    }
}

int main()
{
    rad = NULL;
    CreareBST();
    Inord(rad);
    fout << "\n";
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3010 bst

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3010 bst de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3010 bst