Arbori binari de cautare. Stergerea unui nod

Dupa stergere arborele trebuie sa ramana de cautare.

Fie valoarea 80 a nodului care urmeaza a fi sters. Intervin urmatoarele situatii:

1. nodul care urmeaza a fi sters este nod terminal caz in care se face stergerea (se elibereaza zona de memorie si adresa se inlocuieste cu 0) ceea ce inseamna ca parintele acestuia va avea adresa catre el inlocuita cu 0.

Rezulta:

2. nodul care urmeaza a fi sters subordoneaza un singur subarbore, cel drept, caz in care parintelui sau i se va inlocui adresa catre el cu adresa subarborelui drept respectiv

Rezulta:

3. nodul care urmeaza a fi sters subordoneaza un singur subarbore, cel stang, caz in care parintelui sau i se va inlocui adresa catre el cu adresa subarborelui stang respectiv

4. nodul care urmeaza a fi sters subordoneaza doi subarbori caz in care se procedeaza astfel:

-„in locul” informatiei nodului sters va trece cea mai mare valoare din subarborele sau stang.

Aceasta valoare se gaseste la cel mai din dreapta nod din subarborele stang.

Fie acest nod *f. Fiind cel mai din dreapta inseamna ca acesta va subordona cel mult un subarbore stang. Adresa acestui subarbore „va trece in locul” lui f.

Va rezulta:

O solutie de implementare este:

void cmd(nod* &c,nod* &f)

{nod *aux;

if(f->dr)

cmd(c,f->dr);

else

{c->nr_o=f->nr_o;

aux=f;

f=f->st;

delete aux;

}

}

void sterg(nod *&c,int k)

{nod *aux,*f;

if(c)

if(c->nr_o==k)

if(c->st==0&&c->dr==0) //daca e nod terminal

{delete c;

c=0;

}

else

if(c->st==0) //are numai subordonat drept

{aux=c->dr;

delete c;

c=aux;}

else

if(c->dr==0) //are numai subordonat drept

{aux=c->st;

delete c;

c=aux;}

else

cmd(c,c->st); //are ambii subordonati

else

if(c->nr_o<k)

sterg(c->dr,k);

else

sterg(c->st,k);

else

cout<<"valoarea de sters nu se gaseste in arbore ";

}

void main()

{int i,n,a;

cout<<"nr. de noduri ";

cin>>n;

for(i=1;i<=n;i++)

{cout<<"valoarea de inserat ";

cin>>a;

inserare(v,a);

}

cout<<endl<<"arborele contine urmatoarele noduri "<<endl;

svd(v);

cout<<endl<<"valoarea de sters ";

cin>>a;

sterg(v,a);

cout<<endl<<"arborele contine dupa stergere urmatoarele noduri "<<endl;

svd(v);

getch();

}