În paginile ce urmează am ales să exemplific prin
câteva probleme și prin modul acestora de rezolvare tema abordată în acestă
lucrare – arborii.
1.Se citeste un arbore cu n varfuri dat prin vectorul TATA.
a) Sa se afiseze muchiile arborelui
b) Sa se construiasca si sa se afiseze matricea de adiacenta a arborelui.
Ex: Pentru vectorul de tati 2 0 2 1 3 se vor afisa muchiile [1,2] [2,3]
[1,4] [3,5] si matricea de adiacenta
0 1 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 0 0
0 0 1 0 0
Rezolvare:
#include<iostream.h>
int n, T[100],
a[100][100];
void afis()
{ int i,j;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
void main()
{ int i;
cin>>n;
for(i=1;i<=n;i++) cin>>T[i];
for(i=1;i<=n;i++)
if(T[i]!=0)
{
cout<<"["<<T[i]<<","<<i<<"]
";
a[i][T[i]]=a[T[i]][i]=1;
}
cout<<endl;
afis();
}
2.Se citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se
citeste varful radacina. Sa se construiasca si sa se afiseze vectorul TATA.
Ex: Pentru un arbore cu 5 noduri, cu muchiile [1,2] [2,3] [1,4] [3,5] si
radacina 2 se obtine vectorul de tati 2 0 2 1 3
#include<iostream.h>
int n, r, T[100],
a[100][100], p[100];
void citire()
{ int i,x,y;
cin>>n;
for(i=1;i<=n-1;i++)
{ cin>>x>>y;
a[x][y]=a[y][x]=1;;
}
cin>>r;
}
void BF(int r)
{ int s,d,i,x[100];
d=s=1;
x[1]=r; p[r]=1;
while (s<=d)
{ for(i=1;i<=n;i++)
if(a[x[s]][i] &&!p[i])
{ d++; x[d]=i;
p[i]=1; T[i]=x[s];
}
s++;
}
}
void main()
{ int i;
citire();
BF(r);
for(i=1;i<=n;i++)
cout<<T[i]<<" ";
}
3. Se
citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se citeste
varful radacina. Sa se calculeze si sa se afiseze numarul de niveluri ale
arborelui.
Ex: Pentru un arbore cu 5 noduri si muchiile [1,2] [2,3] [1,4] [3,5]
numarul de niveluri este 3.
#include<iostream.h>
int n,max=0, r, T[100],
a[100][100], p[100];
void citire()
{ int i,x,y;
cin>>n;
for(i=1;i<=n-1;i++)
{ cin>>x>>y;
a[x][y]=a[y][x]=1;;
}
cin>>r;
}
void DF(int r, int niv)
{ p[r]=1;
if(niv>max) max=niv;
for(int i=1;i<=n;i++)
if(a[r][i] &&!p[i])
DF(i,niv+1);
}
void main()
{ int i;
citire();
DF(r,1);
cout<<max;
}
4. Se
citeste un arbore cu n varfuri dat prin vectorul TATA. Sa se afiseze frunzele
arborelui.
Ex: Pentru vectorul de tati 2 0 2 1 3 se vor afisa frunzele 4 si 5.
#include<iostream.h>
int n, T[100], p[100];
void main()
{ int i;
cin>>n;
for(i=1;i<=n;i++)
{ cin>>T[i];
p[T[i]]=1;
}
for(i=1;i<=n;i++)
if(!p[i]) cout<<i<<"
";
}
5. Se
citeste un arbore cu n varfuri dat prin vectorul TATA.
a) Sa se afiseze gradele varfurilor.
b) Sa se afiseze pentru fiecare varf nivelul pe care se afla (numerotarea
nivelelor incepe de la 0-radacina).
Ex: Pentru vectorul de tati 2 0 2 1 3 se vor afisa urmatorii vectori:
Gradele: 2 2 2 1 1
Nivelele: 1 0 1 2 2
#include<iostream.h>
int n,r, T[100], D[100],
p[100], niv[100];
void afis()
{ for(int
i=1;i<=n;i++) cout<<D[i]<<" ";
cout<<endl;
for(i=1;i<=n;i++)
cout<<niv[i]<<" ";
}
void df(int r)
{
for(int i=1;i<=n;i++)
if(T[i]==r && !p[i])
{ p[i]=1;
niv[i]=niv[r]+1;
df(i);
}
}
void main()
{ int i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>T[i];
if(T[i]!=0) { D[i]++;
D[T[i]]++;
}
}
for(i=1;i<=n;i++)
if(T[i]==0) r=i;
niv[r]=0;
df(r);
afis();
}
6. Ce citeste un graf neorientat cu n varfuri si m muchii etichetate prin
costuri (ponderi) pozitive. Graful este dat prin vectorul muchiilor. Se cere sa
se determine un arbore partial de cost minim (are suma costurilor muchiilor
sale minima).
// KRUSKAL
//EFICIENT
#include <fstream>
#include
<algorithm>
using namespace std;
ifstream
fin("apm.in");
ofstream
fout("apm.out");
struct muchie
{
int x,y,c;//c=cost
};
muchie
V[400001],S[400001];//V=vectorul muchiilor, S=muchiile alese
int T[200001];//vector
de "tati"
bool CMP(muchie a,
muchie b)
{
return a.c<b.c;
}
int radacina(int x)
{
if(T[x]==x) return x;
else return T[x]=radacina(T[x]);
}
int main()
{
int n,m,sum=0,k=0;
fin>>n>>m;
for(int i=1;i<=m;i++)
fin>>V[i].x>>V[i].y>>V[i].c;
for(int i=1;i<=n;i++) T[i]=i;
sort(V+1, V+m+1, CMP);//ordonare muchii
crescator dupa cost
for(int i=1;i<=m;i++)
{
if(radacina(V[i].x)!=radacina(V[i].y) )
//muchia nu formeaza ciclu
{ //pt ca
nodurile sunt in subarbori diferiti
T[radacina(V[i].y)]=radacina(V[i].x);//unesc cei 2 subarbori
S[++k]=V[i];//retin muchia
sum+=V[i].c;//maresc suma
costurilor
}
}
fout<<sum<<'\n'<<n-1<<'\n';
for(int i=1;i<=k;i++)
fout<<S[i].x<<'
'<<S[i].y<<'\n';
fin.close();
fout.close();
return 0;
}
//INEFICIENT
#include<fstream.h>
ifstream
fin("k.in");
ofstream
fout("k.out");
struct muchie
{
int x,y,c;
};
muchie a[100];
int
n,m,x[100][100],c[100],p[100],b[100],k,nr;
void citire()
{
fin>>n>>m;
for(int i=1; i<=n;i++)
for(int j=1; j<=n; j++)
x[i][j]=32000;
for(i=1;i<=m;i++)
{
fin>>a[i].x>>a[i].y>>a[i].c;
x[a[i].x][a[i].y]=1;
x[a[i].y][a[i].x]=1;
}
}
void bf(int r,int cul)
{
int s,d,i;
s=d=1;
for(i=1;i<=n;i++) p[i]=0;
b[1]=r;
p[r]=1;
// c[r]=cul;
while(s<=d)
{
for(int i=1;i<=n;i++)
if(!p[i]&&x[b[s]][i]&&c[i]==c[b[s]])
{d++; b[d]=i;
p[i]=1;
c[i]=cul;
}
s++;
}
c[r]=cul;
}
void ordonare()
{
int i,gata;
muchie aux;
do{
gata=1;
for(i=1;i<m;i++)
if(a[i].c>a[i+1].c)
{
aux=a[i];
a[i]=a[i+1];
a[i+1]=aux;
gata=0;
}
}while(!gata);
}
void afis()
{ for(int
k=1;k<=m;k++)
fout<<a[k].x<<"
"<<a[k].y<<" "<<a[k].c<<"\n";
}
int main()
{
citire();
int i;
for(i=1;i<=n;i++) c[i]=i;
ordonare();
//afis();
k=1;nr=0;
do{
if(c[a[k].x]!=c[a[k].y])
{
fout<<a[k].x<<" "<<a[k].y<<"
"<<a[k].c<<"\n";
if(c[a[k].x]<c[a[k].y]) bf(a[k].y,c[a[k].x]);
else
bf(a[k].x,c[a[k].y]);
nr++;
}
k++;
}while(nr<n-1);
}
7. Se
citeste un arbore cu n varfuri dat prin vectorul TATA si apoi un varf k. Sa se
afiseze vectorul TATA obtinut prin mutarea radacinii arborelui in varful k.
#include<iostream.h>
int n,t[100],k;
void citire()
{ cin>>n;
for(int i=1;i<=n;i++) cin>>t[i];
cin>>k;
}
void f(int k)
{ if(t[k]) f(t[k]);
t[t[k]]=k;
}
void afis()
{ for(int
i=1;i<=n;i++) cout<<t[i]<<" ";
}
void main()
{ citire();
f(k);
t[k]=0;
afis();
}
8. Se citeste o padure cu n varfuri prin vectorul de tati. Sa se determine
din cati arbori este formata padurea.
Ex: Pentru vectorul de tati 2 0 2 0 4 5 0 7, padurea este formata 3 arbori.
#include<fstream.h>
ifstream
f("date.in");
ofstream
g("date.out");
int t[100],n;
void citire()
{f>>n;
for(int i=1;i<=n;i++)
f>>t[i];
}
void main()
{citire();
int k=0;
for(int i=1;i<=n;i++)
if(t[i]==0) k++;
g<<k<<" ";
}
9. Se citeste un arbore prin vectorul de tati. Sa se determine si sa se
afiseze cel mai lung lant din arbore.
Ex: Pentru vectorul de tati 2 0 2 5 2 5 3 7 se afiseaza lantul 4 5 2 3 7 8
#include<fstream.h>
fstream fin("date.in",ios::in);
fstream fout("date.out",ios::out);
int
a[20][20],t[100],n,max,mx,my,p[100],f[100];
void citire()
{ int i;
fin>>n;
for(i=1;i<=n;i++)
{fin>>t[i];
f[t[i]]=1;
a[i][t[i]]=1;
a[t[i]][i]=1;
}
}
void df( int r, int niv,int k)
{p[k]=1;
if(niv>max){ max=niv;
mx=r;
my=k;
}
for(int i=1;i<=n;i++)
if( !p[i] && a[k][i])
df(r,niv+1,i);
}
void ff(int r)
{ if(t[r]) ff(t[r]);
t[t[r]]=r;
}
void lant(int r)
{ if(t[r]) lant(t[r]);
fout<<r<<" ";
}
void main()
{ citire();
for(int i=1;i<=n;i++)
if(f[i]==0)
{ for(int j=1;j<=n;j++)
p[j]=0;
df(i,0,i);
}
ff(mx);
t[mx]=0;
lant(my);
}
10. Din fisierul sd.in se citeste un numar natural n reprezentand numarul
de varfuri ale unui arbore binar si apoi vectorii S si D pentru descendentii
fiecarui nod din arbore.
a) Sa se parcurga arborele in preordine, inordine si postordine.
b) Sa se parcurga arborele pe nivele
c) Sa se calculeze si sa se afiseze inaltimea arborelui.
Exemplu:
sd.in
7
2 4 0 0 7 0 0
3 5 6 0 0 0 0
Se va afisa:
Preordine: 1 2 4 5 7 3 6
Inordine: 4 2 7 5 1 3 6
Postordine: 4 7 5 2 6 3 1
Pe nivele: 1 2 3 4 5 6 7
Adancimea: 3
#include<fstream>
using namespace std;
ifstream
fin("sd.in");
ofstream
fout("arb.out");
int
S[100],D[100],P[100],r,n,i,maxx;
void RSD(int n)
{
fout<<n<<" ";
if(S[n]) RSD(S[n]);
if(D[n]) RSD(D[n]);
}
void SRD(int n)
{
if(S[n]) SRD(S[n]);
fout<<n<<" ";
if(D[n]) SRD(D[n]);
}
void SDR(int n)
{
if(S[n]) SDR(S[n]);
if(D[n]) SDR(D[n]);
fout<<n<<" ";
}
void BF(int r)
{
int x[100],i,j;
i=1;j=i;
x[1]=r;
while(i<=j)
{
if(S[x[i]]) x[++j]=S[i];
if(D[x[i]]) x[++j]=D[i];
i++;
}
for(i=1;i<=n;i++) fout<<x[i]<<" ";
}
void adancime(int n, int
niv)
{
if(niv>maxx) maxx=niv;
if(S[n]) adancime(S[n],niv+1);
if(D[n]) adancime(D[n],niv+1);
}
int main()
{
fin>>n;
for(i=1;i<=n;i++) P[i]=0;
for(i=1;i<=n;i++)
{
fin>>S[i];
P[S[i]]=1;
}
for(i=1;i<=n;i++)
{
fin>>D[i];
P[D[i]]=1;
}
for(i=1;i<=n;i++)
if(P[i]==0) r=i;
fout<<"Preordine: ";
RSD(r);
fout<<endl;
fout<<"Inordine: ";
SRD(r);
fout<<endl;
fout<<"Postordine: ";
SDR(r);
fout<<endl;
fout<<"Pe nivele: ";
BF(r);
fout<<endl;
adancime(r,0);
fout<<"Adancimea: ";
fout<<maxx;
fin.close();
fout.close();
return 0;
}