Pagini recente » Cod sursa (job #2670227) | Cod sursa (job #2252049) | Cod sursa (job #2138603) | Cod sursa (job #1809442) | Cod sursa (job #2749855)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
struct nod
{
int val;
nod *stanga, *dreapta;
};
int n;
long long k,ct;
void Preorder(nod * radacina)
{
if(radacina!=nullptr)
{
fout<<radacina->val<<" ";
Preorder(radacina->stanga);
Preorder(radacina->dreapta);
}
}
vector <nod*> allBST(int stanga, int dreapta)
{
//construiesc recursiv toti BST
vector <nod*> bucati;
if(stanga > dreapta)
bucati.push_back(nullptr);
else
{
//vor fi in ordine lexicografica pentru ca valorile se iau de la mic la mare
for(int i=stanga; i<=dreapta && ct<k; ++i) //iau fiecare nod pe rand si-l consider radacina
{
vector <nod*> subStanga=allBST(stanga,i-1);
vector <nod*> subDreapta=allBST(i+1,dreapta);
//conectez radacina cu subarborele stang si cu cel drept
for(int j=0; j<subStanga.size() && ct<k ; ++j)
for(int z=0; z<subDreapta.size() && ct<k ; ++z)
{
nod* radacina=new nod();
radacina->val=i;
radacina->stanga=subStanga[j];
radacina->dreapta=subDreapta[z];
if(dreapta-stanga+1==n) //adaug radacina unui intreg BST cu n noduri
{
ct++;
if(ct==k) // preordinea nr k
bucati.push_back(radacina);
}
else
bucati.push_back(radacina);
}
}
}
return bucati;
}
void allBstPreorders()
{
vector <nod*> radacini=allBST(1,n);
Preorder(radacini[0]); //am pus doar preordinea nr k
}
int main()
{
fin>>n>>k;
allBstPreorders();
return 0;
}