Arbori
Arbori. Definiții. Arbori cu rădăcină
Arbori parțiali de cost minim. Algoritmii Kruskal și Prim
Arbori binari
Heap-uri
Arbori de căutare
Aplicații
Se numește arbore un graf neorientat care este conex și nu conține cicluri. Teoremă: Un graf neorientat cu n noduri este arbore dacă și numai dacă numărul de muchii m=n-1..
Arbore parțial al unui graf neorientat
Se dă un graf neorientat oarecare. Se pune problema să se găsească un graf parțial al său, care să fie arbore. O astfel de structură se numește arbore parțial al unui graf neorientat.
Algoritmul folosește o parcurgere DF. Se afișează numai muchiile selectate, acelea care nu determină cicluri.
Set de cicluri elementare
Se dă un graf neorientat conex cu n noduri. Dacă are n-1 muchii, este arbore și nu conține cicluri. Orice muchie am adăuga la el, graful rămâne conex dar va conține cicluri.
Se pune problema de a se separa cele n-1 muchii ale unui arbore parțial și restul de m-(n-1) muchii care nu fac parte din acesta.
Se folosește parcurgerea df. Muchiile care constituie arborele parțial vor fi muchii de avans, iar cele care sunt în plus vor fi muchii de întoarcere. Muchiile de întoarcere ating noduri deja vizitate. Ele determină cicluri.
Un set de cicluri elementare este un număr de cicluri din graf, astfel încât fiecare ciclu conține cel puțin o muchie care nu mai apare în nici un alt ciclu.
Teoremă: un graf conex conține m-(n-1) cicluri elementare.
Cum fiecare muchie de întoarcere determină un ciclu, înseamnă că avem un set m-(n-1) cicluri în care tocmai muchia de întoarcere este muchia diferită a fiecăruia.
Pentru graful de mai sus, un set de cicluri elementare poate fi:
- 1 2 3 4 1
- 2 3 4 2
- 1 2 3 4 5 1
Dar ciclul 1 2 4 1 nu aparține setului, deoarece toate muchiile sale mai apar și în alte cicluri din set.
Problemă: fiind dat un graf, să se determine un set de cicluri elementare.
Se parcurge prin metoda DF. Se folosește un vector de tați T.
//intr-un graf neorientat cu n noduri si m>n-1 muchii exista m-n+1 cicluri elementare\
c.e. difera prin cel putin o muchie care nu mai apare in nici un alt ciclu = muchia de intoarcere
#include <iostream>
#include <fstream>
using namespace std;
fstream f("setcicluri.txt",ios::in);
int A[10][10],S[10],T[10];
int n,i,j;
void ciclu(int nod)
{
S[nod]=1;
for(int i=1;i<=n;i++)
{
if(A[nod][i]==1)
{
A[i][nod]=0;
if(S[i]==0)
{
T[i]=nod;
ciclu(i);
}
else
{
//un ciclu
int k=nod;
cout<<endl<<nod<<" ";
while(k!=i)
{
cout<<T[k]<<" ";
k=T[k];
}
cout<<nod;
}
}
}
}
//algoritmul este urmatorul: se face o parcurgere DF si se foloseste un vector de tati\
cand se intalneste un nod k vizitat, se afiseaza ciclul inapoi pornind de la nodul curent nod\
si se opreste la nodul de vizitat i.
int main()
{
f>>n;
while(f>>i>>j)A[i][j]=A[j][i]=1;
// S[1]=1;
ciclu(1);
}
Arbori cu rădăcină
Fiind dat un arbore, există posibilitatea să stabilim un nod cu o destinație specială, numit rădăcină a arborelui. Celelalte noduri sunt repartizate în m>=0 seturi disjuncte T1, T2,...Tn și fiecare din aceste seturi este un arbore. Arborii T1, T2, … Tn se numesc subarbori ai rădăcinii.
Într-un arbore cu rădăcină, nodurile sunt așezate pe niveluri, rădăcina fiind pe nivelul 0, celelalte pe nivele crescătoare: 1, 2, etc.
Dacă nodurile i și j sunt adiacente, atunci nodul aflat pe un nivel superior (deci nivel mai mic) se numește tată (ascendent), iar celălalt se numește fiu (descendent).
Memorarea arborilor cu rădăcină folosind referințe descendente.
Se construiește o structură care conține informația asociată nodului (numărul nodului) și informațiile de adresă pentru fii.
Observații: 1. Pentru un arbore oarecare nu se cunoaște numărul fiilor. Cum numărul maxim de descendenți posibili este n-1, structura trebuie să prevadă posibiliotatea a n-1 descendenți. Pentru descendenții care nu există, structura va memora valoarea 0.
2. Din acest motiv, metoda referințelor descendente nu este folosită pentru grafurile oarecare, ci numai pentru un tip particular de arbori cu rădăcină, arborii binari, care au maxim 2 descendenți.
Memorarea prin liste de adiacență
Este un procedeu identic cu cel folosit la grafurile neorientate.
Memorarea prin referințe ascendente
Se construiește un vector de tați T, care va memora pentru fiecare nod i o valoare în T[i] egală cu tatăl nodului i. Deci T[i] = j, dacă j este tatăl lui i, sau 0, dacă i este rădăcină.
Înălțimea unui arbore cu rădăcină
Dacă rădăcina are nivelul 0, descendenții ei sunt pe nivelul 1, descendenții nodurilor de pe nivelul 1 sunt pe nivelul 2, ș.a.m.d.
Înălțimea unui arbore cu rădăcină este cel mai mare nivel pe care se află un nod al său.
Arborele din figura de mai sus are înălțimea 2.
Problemă: se dă un arbore. Se cere să se afișeze, pentru fiecare nod, nivelul pe care se află.
Noțiunea de pădure
O pădure este o mulțime de 1<=k<=n arbori cu nodurile cuprinse în mulțimea (1,2,3,... n). Mulțimile nodurilor celor k arbori alcătuiesc o partiție a mulțimii (1, 2,... n).
O pădure poate fi reprezentată printr-un singur vector Tata.
Arbori parțiali de cost minim
Fie G=(V, E) un graf neorientat, conex. Fiecare muchie (i, j) are asociat un cost c(i,j)>=0. Se cere un arbore parțial al lui G, astfel încât suma costului muchiilor sale să fie minimă.
Acest arbore se numește arbore parțial de cost minim.
Există doi algoritmi pentru a rezolva această problemă: algoritmul lui Kruskal, cu complexitatea O(m*log m) și algoritmul lui Prim, cu complexitatea O(n^2). Dacă numărul muchiilor este mic, se va prefera Kruskal. Dacă numărul de muchii este mare, se preferă Prim. Ambii algoritmi se încadrează la metoda Greedy.
Algoritmul lui Kruskal
Inițial, fiecare nod va constitui un arbore, deci vom avea o pădure alcătuită din n arbori.
Se execută de n-1 ori: Caută muchia de cost minim care unește noduri care aparțin la doi arbori diferiți și se selectează această muchie.
După selectarea a n-1 muchii, se obține un arbore parțial de cost minim.
Implementarea algoritmului: este nevoie de un vector de tați pentru reținerea pădurii. Pentru a se asigura muchia de cost minim, este nevoie ca să se facă o sortare a muchiilor. Memorarea grafului se va face prin lista muchiilor, în fapt o matrice cu m*3 elemente. Pentru fiecare muchie se va memora i, j, c - unde i și j sunt nodurile, iar c este costul muchiei.
/* construieste arborele de cost minim al unui graf neorientat
graful se reprezinta in memorie prin lista muchiilor, tabloul M[10][3]
arborele se reprezinta prin referinte ascendente utilizant vectorul de tati T
inaltimile se memoreaza in vectorul H
muchiile se sorteaza prin algoritmul quicksort
se aleg n-1 muchii in ordinea crescatoare a costului astfela incat sa uneasc[ 2 arbori diferiti
arborele mai scurt se subordoneaza arborelui mai inalt
*/
#include <iostream>
#include <fstream>
using namespace std;
fstream f("kp.txt",ios::in);
int m,n,i,j,a,b,c;
int M[10][3];
int T[10],H[10];
int rad(int nod)
{
while(T[nod])
nod=T[nod];
return nod;
}
void schimba(int p,int q)
{
int a=M[p][0];
int b=M[p][1];
int c=M[p][2];
M[p][0]=M[q][0];
M[p][1]=M[q][1];
M[p][2]=M[q][2];
M[q][0]=a;
M[q][1]=b;
M[q][2]=c;
return;
}
void sm(int inf,int sup)
{
if(inf<sup)
{
int pivot=M[inf][2];
i=inf+1,j=sup;
while(i<=j)
{
while(i<=sup&&M[i][2]<=pivot)i++;
while(j>=inf&&M[j][2]>pivot)j--;
if(i<j)
{
schimba(i,j);
i++;
j--;
}
}
i--;
schimba(inf,i);
sm(inf,i-1);
sm(i+1,sup);
}
}
void sortaremuchii()
{
sm(1,m);
}
int main()
{
f>>n; //nr de noduri
i=0;
while(f>>a>>b>>c)
{
i++;
M[i][0]=a;
M[i][1]=b;
M[i][2]=c;
}
m=i; //nr de muchii
cout<<n<<" "<<m;
sortaremuchii();
for(i=1;i<=m;i++)
cout<<endl<<M[i][0]<<" "<<M[i][1]<<" "<<M[i][2];
cout<<endl<<"lista muchiilor selectate"<<endl;
//selectam muchia 1 si desemnam nodul M[1][0] radacina arborelui de cost minim
T[M[1][1]]=M[1][0];
H[M[1][0]]=1;
c=M[1][2]; //costul total al arborelui
cout<<M[1][0]<<" "<<M[1][1]<<" "<<M[1][2];
i=2; //contor in M
j=2; //contor muchii selectate
while(j<=n-1&&i<=m)
{
a=M[i][0];
b=M[i][1];
int ra=rad(a);
int rb=rad(b);
if(ra!=rb)
{
//anexam muchia i la arbore
//comparam inaltimile arborilor
j++;
cout<<endl<<M[i][0]<<" "<<M[i][1]<<" "<<M[i][2];
c+=M[i][2];
if(H[ra]<H[rb])
{
//atasare nod a la radacina arb rb
T[ra]=rb;
}
else
{
if(H[ra]>H[rb])
{
//anexare nod b la radacina ra
T[rb]=ra;
}
else
{
//inaltimi egale, se subordoneaza rb la ra si H[ra]++
T[rb]=ra;
H[ra]++;
}
}
}
i++;
}
cout<<endl<<"cost arbore de cost minim="<<c;
}
Algoritmul lui Prim
Se pornește de la un nod al grafului.
Se execută de n-1 ori: se adaugă la arborele obținut la pasul anterior o muchie de cost minim, dintre cele care au o singură extremitate în arborele obținut la pasul anterior.
Graful se memorează sub forma matricii costurilor. Se folosește un vector de selecție S.
//algoritmul lui Prim varianta 1\
construieste un arbore de cost minim prin selectarea \
muchiilor care au o extremitate in arbore si alta nu\
deci S[i]=1 si S[j]=0. Se selecteaza intotdeauna muchia de cost minim\
care indeplineste conditia
#include <iostream>
#include <fstream>
using namespace std;
fstream f("kp.txt",ios::in);
int A[50][50],S[50];
int n,i,j,c,cost=0,valmin,imin,jmin;
const int MINIM=0xffff;
int main()
{
cout<<endl<<"Algoritmul lui Prim 1";
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)A[i][j]=A[j][i]=MINIM;
else
A[i][j]=0;
while(f>>i>>j>>c)A[i][j]=A[j][i]=c;
//se selecteaza nodul 1
S[1]=1;
//se vor selecta n-1 muchii
int k=1;
valmin=MINIM, jmin=1,imin=1;
while(k<=n-1)
{
valmin=MINIM;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(S[i]==1&&S[j]==0&&A[i][j]!=0&&A[i][j]<valmin)
{
valmin=A[i][j];
imin=i;
jmin=j;
}
cout<<endl<<imin<<" "<<jmin<<" cost "<<A[imin][jmin];
cost+=A[imin][jmin];
S[jmin]=1;
k++;
}
cout<<endl<<"cost total Prim1="<<cost;
cout<<endl<<"Algoritmul lui Prim 2";
for(i=1;i<=n;i++)S[i]=0;
cost=0;
//selectare nodul 1
k=1;
//toate celelalte noduri se considera adiacente cu nodul 1
for(i=2;i<=n;i++)S[i]=1;
while(k<=n-1)
{
//se cauta nodul adiacent aflat la distanta minima de un nod selectat
valmin=MINIM;
for(i=1;i<=n;i++)
{
if(S[i]!=0&&A[i][S[i]]<valmin)
{
valmin=A[i][S[i]];
imin=i;
}
}
//se selecteaza nodul imin, adiacent cu S[i]
jmin=S[imin];
cout<<endl<<imin<<" "<<jmin<<" cost "<<valmin;
cost+=valmin;
S[imin]=0;
//actualizare S
for(i=1;i<=n;i++)
if(S[i]!=0&&A[i][S[i]]>A[i][imin])
S[i]=imin;
k++;
}
cout<<endl<<"cost total Prim2="<<cost;
}
#include <iostream>
#include <fstream>
using namespace std;
fstream f("kp.txt",ios::in);
int n,i,j,c;
const int nrmax=0xffff;
int A[10][10];
int S[10];
/* construieste arborele de cost minim pentru un graf neorientat
graful este reprezentat prin matricea costurilor forma 1
se incepe cu nodul 1 la care se adauga celelalte n-1 noduri prin muchii in ordinea costurilor
astfel incat o muchie sa aibă unul din noduri in arbore iar celalalt in afara arborelui.
ciclul s erepeta de n-1 ori, iar in fiecare ciclu cautarea se face in n*n operatii
complexitate algoritm=O(n**3).
*/
int main()
{
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
A[i][j]=nrmax;
while(f>>i>>j>>c)
A[i][j]=A[j][i]=c;
S[1]=1;
c=0;
for(int k=1;k<=n-1;k++)
{
int l=nrmax;
int sel=1,seli=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(S[i]==1&&S[j]==0)
{
if(A[i][j]<l)
{
l=A[i][j];
seli=i;
sel=j;
}
}
}
c+=l;
S[sel]=1;
cout<<endl<<seli<< " "<<sel;
}
cout<<endl<<"cost total arbore ="<<c;
}
Arbori binari
Arbori binari
Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult doi descendenți: cel stâng și cel drept.
Spre deosebire de grafurile neorientate obișnuite, la arborii binari contează poziția relativă a nodurilor. Astfel, cele două grafuri din figura următoare sunt diferite.
Definiție: Un arbore binar este un set finit T, de unul sau mai multe noduri, astfel încât:
- Există un nod special numit rădăcina arborelui binar;
- Celelalte noduri sunt repartizate în 2 seturi disjuncte T1 și t2, și fiecare din aceste seturi este un arbore binar. Arborii t1 și T2 se numesc subarborii rădăcinii. T1 se numește subarborele stâng, iar t2 se numește subarborele drept.
Proprietăți:
- Există cel mult 2^i noduri pe nivelul i al arborelui.
- Un arbore binar de înălțime h are cel mult 2^h noduri pe ultimul nivel. Ultimul nivel este h.
- Un arbore binar cu înălțimea h are cel mult 2^(h+1)-1 noduri.
- Într-un graf cu n noduri și înălțimea h, avem relația: h>=log₂(n+1)-1.
- Dacă a este numărul nodurilor terminale (care nu mai au descendenți) și c este numărul nodurilor care au exact 2 descendenți, atunci a=c+1. Demonstrație: notăm b=numărul nodurilor cu un singur descendent. a+b+c=n; m=n-1; suma gradelor exterioare = m=n-1; b+2c=n-1 ⇔ a=c+1.
De demonstrat relațiile 1-4 de mai sus.
Modalități de reprezentare a arborilor binari
Referințe ascendente (vectorul Tata)
La fel ca în cazul arborilor oarecare.
Referințe descendente
Pentru fiecare nod trebuie să se cunoască nodul descendent stâng și nodul descendent drept. O metodă este prin folosirea a doi vectori, st și dr. pentru fiecare nod i, st[i] deține descendentul stâng, iar dr[i] descendentul drept.
Structuri alocate dinamic în HEAP
Definim o structură:
Struct nod
{
Int nr;
nod* stg, * drt;
};
Aceasta este cea mai utilizată formă de reprezentare a arborilor binari.
Modalități de parcurgere a arborilor binari
Există 3 modalități consacrate de parcurgere:
- Parcurgerea în inordine (SVD) - separcurge mai întâi subarborele stâng, apoi vârful, apoi subarborele drept;
- Parcurgerea în preordine (VSD)- se vizitează întâi vârful, apoi s.a. Stâng, apoi s.a. Drept;
- Parcurgerea în postordine (SDV) - întâi s.a stâng, apoi s.a. Drept, apoi rădăcina.
Problemă rezolvată: să se creeze un arbore binar, apoi să se listeze nodurile utilizând toate modalitățile de parcurgere.
/*
sa se creeze un arbore binar pornind de la parcurgerea inordine si preordine
din fisier se citesc nodurile in parcurgere inordine
nodurile in parcurgere preordine sunt in ordine naturala 1,2,... n.
*/
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int inord[50];
int n=0;
typedef struct nod
{
int inf;
nod* st;
nod* dr;
} nod;
typedef nod* arb;
void SVD(arb karb) //parcurgere inordine
{
if(karb!=0)
{
SVD(karb->st);
cout<<karb->inf<<" ";
SVD(karb->dr);
}
}
void VSD(arb karb) //parcurgere preordine
{
if(karb!=0)
{
cout<<karb->inf<<" ";
VSD(karb->st);
VSD(karb->dr);
}
}
arb creare(int rad,int st,int dr)
{
//st si dr reprezinta sectiunea din inord[] care contine un subarbore\
acest subarbore va avea obligatoriu radacina rad=st fiind primul nod din parcurgerea preordine\
se cauta rad in inord, fie poz indicele lui rad\
poz separa vectorul in 2 segmente\
segm stang cuprinde nodurile st... poz-1 si va avea radacina pe pozitia st+1\
segm drept cuprinde nodurile poz+1... dr si va avea radacina pe pozitia st+poz
//cout<<endl<<rad;
arb v=new nod;
v->inf=rad;
int poz=st;
for(poz=st;inord[poz]!=rad;poz++);
//inord[poz]=rad
if(poz==st)
//subarb stang vid
v->st=0;
else
v->st=creare(rad+1,st,poz-1);
if(poz==dr)//sa drept vid
v->dr=0;
else
v->dr=creare(rad+poz-st+1,poz+1,dr); //sar din pozitia rad peste nr de elemente ale subarb stang = poz-st si urmatorul e noua radacina
return v;
}
int main()
{
int a;
while(f>>a)
inord[++n]=a;
arb barb=creare(1,1,n);
cout<<endl<<"parcurgere preordine"<<endl;
VSD(barb);
cout<<endl<<"parcurgere inordine"<<endl;
SVD(barb);
cout<<endl<<barb->inf;
}
Arbore binar plin
Definiție: Se numește arbore binar plin, un arbore binar unde pe fiecare nivel i din intervalul 0, 1, 2, ...h, unde h este înalțimea arborelui, se găsesc exact 2^i noduri.
Proprietăți:
1. un arbore binar plin cu înălțimea h are 2^(h+1)-1 noduri.
2. Un arbore binar plin cu n noduri are înălțimea log₂(n+1)-1.
Raportat la numărul de noduri, arborele binar plin are înălțimea minimă. Majoritatea algoritmilor de prelucrare a arborilor binari (căutare, parcurgere, etc) sunt cu atât mai eficienți, cu cât înălțimea arborelui este mai mică. Arborii binari plini sunt însă rari, deoarece numărul de noduri trebuie să fie de forma 2^(h+1)-1. În loc de arbori plini, se vor utiliza întotdeauna arbori compleți.
Arbore binar complet
Definiție: un arbore binar complet este un arbore în care fiecare nivel în afară de ultimul are exact 2^i noduri (fiecare nod are exact 2 descendenți). Ultimul nivel h este incomplet, dar are toate nodurile grupate fie la stânga, fie la dreapta arborelui.
Proprietăți:
- Toate nodurile terminale se găsesc pe ultimele două niveluri;
- h=[log₂n] unde [...] este partea întreagă.
Reprezentare: un arbore binar complet cu n noduri poate fi reținut cu ajutorul unui vector v cu n componente, astfel:
- Rădăcina este dată de valoarea reținută de v[1].
- Dacă nodurile de pe nivelul ultim sunt grupate la stânga, pentru nodul v[i], vârful subarborelui stâng este v[2i] și vârful subarborelui drept este v[2i+1]. Dacă nodurile de pe ultimul nivel sunt grupate la dreapta, reprezentarea este inversă: vârful subarborelui drept este în v[2i] și următorul v[2i+1] este vârful subarborelui stâng.
Min-Heap și Max-heap
Definiție: un vector v se numește MinHeap dacă el este reprezentarea unui arbore binar complet cu proprietatea că oricare nod are o valoare mai mică decât valorile fiilor săi (orice nod subordonează noduri cu etichete mai mari). Analog, vectorul se numește MaxHeap dacă este reprezentarea unui arbore binar complet cu proprietatea că oricare nod este mai mare decât fii săi (orice nod subordonează nbodurio cu etichete mai mici).
Relația matematică este: pentru minheap: pentru orice i cuprins între 1 și n/2, v[i]<=v[2i] și v[i]<= v[2i+1]. Pentru maxheap, relația este inversă: v[i]>=v[2i] și v[i]>= v[2i+1].
Probleme: 1. dacă vectorul v conține un minHeap și modificăm valoarea reținută în v[1], se cere să se reorganizeze v ca minHeap.
2. Se citește un vector cu n componente numere naturale. Să se organizeze vectorul ca minheap.
3. HeapSort. Se citește un vector cu n componente numere natuirale. Să se ordoneze descrescător.
/* crearea unui maxheap prin inserare
organizarea unui vector ca maxheap
sortare heap-sort
*/
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int minhp[20],maxhp[20],sorthp[20];
int n=0;
void reorghp(int p,int n)
{
int tata=p;
int fiu=p*2;
while(fiu<=n)
{
if(fiu<n)
if(minhp[fiu+1]>minhp[fiu])
fiu=fiu+1;
if(minhp[tata]<minhp[fiu])
{
int aux=minhp[tata];
minhp[tata]=minhp[fiu];
minhp[fiu]=aux;
tata=fiu;
fiu=tata*2;
}
}
}
void insertheap(int v,int n)
{
int fiu=n+1;
int tata = fiu/2;
while(tata&&minhp[tata]>v)
{
minhp[fiu]=minhp[tata];
fiu=tata;
tata=fiu/2;
}
minhp[fiu]=v;
}
int main()
{
int a;
while(f>>a)
{
insertheap(a,n);
n++;
}
for(int i=1;i<=n;i++)
cout<<minhp[i]<<" ";
cout<<endl;
for(int i=n/2;i>=1;i--)
reorghp(i,n);
for(int i=1;i<=n;i++)
cout<<minhp[i]<<" ";
cout<<endl;
}
Soluția 2
/* citeste un sir de numere si il sorteaza prin metoda heapsort
algoritmul combinare
*/
#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
int n=0;
int *V;
void reorganizare(int p,int q)
{
int tata=p;
int fiu=2*p;
if(fiu<=q)
{
if(fiu<q)
{
if(V[fiu]>V[fiu+1]) fiu++;
}
if(V[tata]>V[fiu])
{
int aux=V[tata];
V[tata]=V[fiu];
V[fiu]=aux;
reorganizare(fiu,q);
}
}
}
int main()
{
V=new int[20];
int a;
while(f>>a)
V[++n]=a;
{
//reorganizez V ca minheap intre indicii [i si n]
for(int j=n;j>=1;j--)
{
for(int i=(j)/2;i>=1;i--)
reorganizare(i,j);
int a=V[1];
V[1]=V[j];
V[j]=a;
}
}
for(int i=1;i<=n;i++)
cout<<V[i]<<" ";
}
Arbori de căutare
Definiție. Se numește arbore de căutare un arbore binar în care fiecare nod are o cheie unică de identificare care respectă condițiile următoare:
- Orice cheie asociată unui nod al subarborelui stâng este mai mică decât cheia asociată nodului;
- Orice cheie asociată unui nod al subarborelui drept este mai mare decât cheia asociată nodului.
Operațiile care se pot executa asupra unui arbore de căutare sunt:
- Inserarea. Se dă o valoare oarecare și adresa unui vârf al unui arbore de căutare (arborele este reprezentat prin structuri “nod” alocate dinamic, iar adresa nodului din vârf este cunoscută printr-un pointer). Dacă arborele este nevid, atunci avem posibilitățile următoare:
- Valoarea coincide cu cheia vârfului - se renunță la adăugare;
- Valoarea este mai mică decât cheia vârfului - se reia problema pentru subarborele stâng;
- Valoarea este mai mare decât cheia nodului - se reia problema pentru s.a. Drept;
- Altfel (dacă nodul este vid) se creează nodul care are drept cheie valoarea respectivă și se leagă de părinte, la dreapta sau la stânga, după caz.
- Căutarea. Dacă arborele este nevid și cheia coincide cu eticheta vârfului, am rezolvat problema. Dacă cheia este mai mică, vom căuta în s.a. Stâng, iar dacă este mai mare, căutăm în s.a. Drept. Dacă arborele este vid, cheia căutată nu există în arbore.
- Ștergerea. Dacă există un nod cu cheia egală cu valoarea căutată, să se șteargă acel nod. Regula este următoarea:
- Valoarea coincide cu cheia vârfului - valoarea există în arbore. Dacă nodul este terminal (s.a stâng și s.a. drept sunt vizi), nodul este șters iar adresa reținută de părinte pentru el este nulă. Dacă valozarea este mai mică decât cheia vârfului, se reia problema pentru s.a stâng, altfel se reia pentru s. a drept.
- Dacă numai s.a drept este nevid, atunci nodul este șters, iar părintele lui va reține, în locul adresei lui, adresa s.a. drept.
- Dacă numai s.a. Stâng este nevid, nodul este șters, iar părintele lui va reține, în locul adresei lui, adresa s.a. drept.
- Dacă ambii s.a stâng și drept sunt nevizi, se identifică cel mai din dreapta nod al s.a. Stâng, cheia nodului astfel identificat este memorată în nodul analizat, iar ndul identificat se șterge ca și în situația în care ar avea numai s.a. stâng.
Problema rezolvată
/* arborii de cautare sunt arbori binari in care descendentul stang<radacina<descendentul drept
operatiile care se fac asupra a.c. sunt
crearea
parcurgerea
cautarea
stergerea
se foloseste alocarea dinamica si structura de nod
*/
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
fstream f("arbc.txt",ios::in);
typedef struct nod
{
int val;
nod* st;
nod *dr;
} nod;
nod *varf,*tata;
int v,n,dir;
nod* cre_nod(int v)
{
nod* nd=new nod;
nd->val=v;
nd->st=nd->dr=NULL;
return nd;
}
void ins_nod(int v,nod* tata)
{
if(v<tata->val)
{
if(tata->st)
ins_nod(v,tata->st);
else
{
tata->st=cre_nod(v);
}
}
else
if(v>tata->val)
{
if(tata->dr)
ins_nod(v,tata->dr);
else
tata->dr=cre_nod(v);
}
}
void listare(nod* vf)
{
if(vf->st)
listare(vf->st);
cout<<vf->val<<" ";
if(vf->dr)
listare(vf->dr);
}
bool cautare(int v,nod* vf) //pune in var globala nod* tata pointer la tata si in int dir directia spre nodul gasit
{
if(vf)
if(vf->val==v) return true;
else
if(v<vf->val)cautare(v,vf->st);
else
cautare(v,vf->dr);
}
void stergere(int v,nod* &vf) // tot skepsisul e & caci se transmite prin adresa pointerul
{
if(vf)
{
nod* man;
if(v<vf->val)stergere(v,vf->st);
else
if(v>vf->val)stergere(v,vf->dr);
else
{
if(vf->st==0&&vf->dr==0)
{
delete vf;
vf=0;
}
else
if(vf->st==0)
{
man=vf->dr;
delete vf;
vf=man;
}
else
if(vf->dr==0)
{
man=vf->st;
delete vf;
vf=man;
}
else
{
man=vf->st;
while(man->dr)
{
man=man->dr;
}
int temp=man->val;
stergere(man->val,vf);
vf->val=temp;
}
}
}
}
int main()
{
f>>v;
varf=cre_nod(v); //radacina se creaza separat
while(f>>v)
{
ins_nod(v,varf);
}
cout<<endl;
listare(varf);
cout<<"care nod sa sterg in plm? ";
cin>>v;
bool gasit=cautare(v,varf);
if(!gasit)
cout<<endl<<"nodul cautat nu exista in plm!";
else
stergere(v,varf);
listare(varf);
}
Niciun comentariu:
Trimiteți un comentariu