constructie vectorul TATA

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.

vector_tata2noduri1

Vectorul de tati de declara astfel: T[i]=parintele(tata) nodului i.

Pentru arborele din figura vectorul TATA este 0,1,2,1 si radacina este 1.Muchiile care se citesc sunt 1-2,2-1,1-4

#include<iostream.h>
int n, r, T[20], a[20][20], p[20];void citire()
{ int i,x,y;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“cititi muchiile de forma x-y : “<<endl;
  for(i=1;i<=n-1;i++)
    { cin>>x>>y;
      a[x][y]=a[y][x]=1;;
    }
  cout<<“dati radacina : “<<endl;
  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);
  cout<<“vectorul TATA este :”<<endl;
  for(i=1;i<=n;i++) cout<<T[i]<<” “;
}

arbori binari vector TATA

Se citeste un arbore cu n varfuri dat prin vectorul TATA.
1) Sa se afiseze muchiile arborelui
2) Sa se construiasca si sa se afiseze matricea de adiacenta a arborelui.

noduri1vector_tata1

Observatie: vectorul TATA  precizeaza pentru fiecare varf i, nodul TATA[i] care reprezinta parintele sau

Pentru arborele din imagine vectorul TATA este: 0,1,2,1.

#include<iostream.h>
int n, t[20], a[20][20];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;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“dati vectorul tata “<<endl;
  for(i=1;i<=n;i++)
  {
  cout<<“t[“<<i<<“]=”;
  cin>>t[i];
  }
  cout<<“muchiile sunt: “<<endl;
  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;
  cout<<“matricea de adiacenta este: “<<endl;
  afis();
}

parcurgere arbore binar

Sa se parcurga un arbore binar

 

#include<iostream.h>
#include<conio.h>
struct nod
{int nr;
nod* st,*dr;
};
nod *c;
int nrst,nrdr;

void svd(nod *c)
{
if(c)
{svd(c->st);
cout<<c->nr;
svd(c->dr);
}
}

void vsd(nod *c)
{
if(c)
{cout<<c->nr;
vsd(c->st);
vsd(c->dr);
}}

void sdv(nod *c)
{
if(c)
{
sdv(c->st);
sdv(c->dr);
cout<<c->nr;
}
}

nod *arb()
{int n;
nod *c;
cout<<“n=”;cin>>n;
if(n)
{
c=new nod;
c->nr=n;
c->st=arb();
c->dr=arb();
return c;
}
else return 0;
}

void main()
{
clrscr();
c=arb();
svd(c);
cout<<endl;
vsd(c);
cout<<endl;
sdv(c);
cout<<endl;
getch();
}