Stergerea Unui Nod Dintr_Un Arbore Binar De Cautare

[+skyler_sdf]

Se creeaza un arbore binar de cautare. Sa se stearga un nod dat.

In exemplul de mai jos am folosit instructiunea switch pentru 1.inserare, 2.parcurgere, 3.stergere

Obs: dupa stergerea unui nod care are o anumita cheie, arborele ramas trebuie sa fie de cautare.

#include<iostream.h>

#include<conio.h>

struct nod{

int info;

nod *dr, *st;

};

nod *v, *aux;

int n;

int opt;

//creeaza arborele binar de cautare

void inserare(nod *&c, int n)

{

if(c)

if(c->info==n)

cout<<"nod deja inserat. inserati altul!";

else

if(c->info<n)

inserare(c->st, n);

else

inserare(c->dr, n);

else

{

c=new nod;

c->dr=c->st=0;

c->info=n;

}

}


void parcurg(nod *c)

{

if(c)

{

parcurg(c->dr);

cout<<c->info<<" ";

parcurg(c->st);

}

}

//in cazul in care un nod care urmeaza a fi sters, subordoneaza doi arbori, se apeleaza functia _supl

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

{

if(f->st)

functie_supl(c, f->st);

else

{

c->info=f->info;

aux=f;

f=f->dr;

delete aux;

}

}

//pe langa cele 3 cazuri(nod din subarborele stang care nu subordoneaza nici un alt arbore, nod din subarborele stang care subordoneaza un subarbore-drept,

// nod din subarborele drept-cel mai din dreapta nod al subarborelui stang, 

// in ultimul caz: nod din subarborele drept-cel mai din dreapta nod al subarborelui stang

//se identifica nodul cel mai din dreapta din subarborele stang(care este cu cheia cea mai mare din acest subarbore

//cheia acestuia trece in locul cheii nodului care se sterge

//aceasta este mai mica decat cheia initiala (ptr ca se gaseste in subarborele stang) este in acelasi timp cea mai mare din subarborele stang

//deci este cea mai mare cheie din subarborele stang care este mai mica decat cheia care se sterge

void sterg(nod *&c, int n)

{

nod *f;

if(c)

if(c->info==n)

if(c->dr==0 && c->st==0) 

{

delete c;

c=0;

}

else

if(c->dr==0) 

{

f=c->st;

delete c;

c=f;

}

else

if(c->st==0)

{

f=c->dr;

delete c;

c=f;

}

else

functie_supl(c, c->dr);

else

if(c->info<n)

sterg(c->st, n);

else

sterg(c->dr, n);

else

cout<<"eroare";

}

void main()

{

v=0;

do{

	cout<<"dati optiune:";

cin>>opt;

switch(opt)

{

case 1:

cout<<"dati nodul: ";

cin>>n;

inserare(v, n);

break;

case 2:

parcurg(v);

break;

case 3:

cout<<"dati nodul pe care il sterg: ";

cin>>n;

sterg(v, n);

break;}

}while(opt!=4);

getch();

}