Arbori binari ordonati (ABO). Tehnici de suprimare a nodurilor din ABO

1. Scopul lucrarii il constituie prezentarea operatiei de suprimare a unui nod din structura de arbore binar ordonat, in implementarea cu pointeri.

2. Aspecte teoretice.

Pentru a suprima nodul cu cheia x dintr-un arbore binar ordonat, mai intai se cauta daca exista un astfel de nod in arbore. Daca nu, suprimarea s-a incheiat. In caz ca nodul exista, atunci se suprima nodul, procedandu-se de o asemenea maniera incat arborele sa ramana ordonat si in urma suprimarii.

In procesul de suprimare se disting doua cazuri, dupa cum nodul de suprimat are cel mult un fiu sau are doi fii, si anume:          

Daca nodul de suprimat are cel mult un fiu: in aceasta situatie referinta care indica spre nodul de suprimat (un camp al tatalui nodului de suprimat sau, in cazul radacinii, referinta spre radacina), se modifica astfel incat sa indice unicul fiu al nodului de suprimat, daca acesta exista, sau in caz contrar, valoarea lui devine NULL.

- Daca nodul de suprimat are doi fii:

- se cauta predecesorul nodului in ordonarea in inordine. Se poate demonstra ca acest nod exista si ca el nu are fiu drept;

- se modifica nodul de suprimat asignand toate campurile sale de date cu campurile corespunzatoare ale predecesorului. In acest moment predecesorul se gaseste in dublu exemplar in structura de arbore: in locul sau initial si in locul nodului de suprimat;

- se suprima predecesorul conform cazului anterior, deoarece acesta nu are fiu drept. 

Predecesorul Y al unui nod X se poate detecta prin urmatoarea metoda: se construieste o secventa de noduri care incepe cu fiul stang al lui X, dupa care se alege drept succesor al fiecarui nod, fiul sau drept. Primul nod al secventei care nu are fiu drept este predecesorul.

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

Functiile urmatoare realizeaza stergerea unui nod dintr-un arbore binar ordonat:

void CopStergPred(struct _nodABO **p, struct

_nodABO *q)

void StergNod(struct _nodABO **p, int x)else//are cel mult fiu stang

if((*p)->dr==NULL)else //are 2 fii

CopStergPred(&(*p)->st, q);

}

Functia StergNod realizeaza suprimarea nodului cu cheia x in arborele a carui radacina este indicata de p. Suprimarea presupune in prealabil cautarea nodului in arbore. In momentul in care acesta este gasit, se realizeaza suprimarea propriu-zisa, in functie de cazul in care nodul are cel mult un fiu sau doi fii. Functia CopStergPred cauta predecesorul, il copiaza ca informatii utile in locul nodului de sters si apoi il suprima pe predecesor (conform secventei de pasi descrisa pentru cazul al doilea). Ea se utilizeaza numai in cazul in care nodul X are doi fii.

3. Problema rezolvata

Se presupune ca multimea de studenti dintr-un an este memorata sub forma unei structuri de arbore binar ordonat, in functie de numele studentilor. Pentru fiecare student se cunoaste media pe sesiunea din iarna. Sa se construiasca un alt arbore binar care sa cuprinda numai studentii care doresc bilet de tabara, extragandu-i din arborele initial si pastrand in acesta doar pe ceilalti studenti. Sa se afiseze studentii care doresc bilete ordonati descrescator dupa medii, iar ceilalti - alfabetic.

Rezolvare

Arborele initial cuprinde toti studentii ordonati dupa nume (in ordine alfabetica). La fiecare pas utilizatorul da numele unui student care a depus cerere. Acesta va fi cautat in arborele initial. Daca nu s-a gasit, se semnaleaza acest lucru; daca s-a gasit, functia Cauta ne va returna referinta din arbore spre el. Nodul trebuie eliminat din arborele initial, dar intrucat el trebuie inserat in noul arbore, nu efectuam stergerea fizica a lui, ci doar extragerea sa din arbore. Functia de extragere si reinserare, Imparte, este similara cu cea de stergere prezentata in partea teoretica, doar ca nu sterge fizic nodul, ci pastreaza adresa lui si apeleaza apoi inserarea lui in noul arbore. Functia de inserare, InsertieNod, insereaza in noul arbore nodul in mod descrescator dupa medii.

Pentru crearea arborelui initial se foloseste un fisier care contine numele si mediile studentilor.

#include <stdio.h>

#include <conio.h>

#include <string.h>

typedef struct _nodABOnodABO;

nodABO *rad, *radN, **pp;

FILE *f;

char s[100];

float medie;

//adaugarea in arbore alfabetic

void AdaugNod(nodABO **p)

else

//afisare arbore ca lista

void AfisCaLista(nodABO *p)

//cauta nod cu cheia s in arbore alfabetic

nodABO **Cauta(nodABO **p)

return p;

//insertie nod in arbore descrescator dupa medii

void InsertieNod(nodABO **p, nodABO *q)

else

//intoarce adresa predecesorului, dupa ce-l scoate din arbore

nodABO *Predecesor(nodABO **p)

//muta nodul primit ca parametru din arborele initial in celalalt

void Imparte(nodABO **p)

//inseram in noul arbore nodul de mutat

InsertieNod(&radN, q);

void StergABO(nodABO *p)

int main(void)

fscanf(f, '%d', &nr);

for(i=0;i<nr;i++)

fclose(f);

do

}

}while(s[0]!='0');

StergABO(rad); //stergere arbore initial

StergABO(radN); //stergere arbore cu doritori

return 0;

4. Probleme propuse

4.1. Catalogul unei biblioteci de fisiere este organizat ca si o structura de arbore binar ordonat (functie de numele fisierului). Fiecare nod se refera la un fisier si contine numele fisierului, data crearii, dimensiunea fisierului precum si alte informatii. Sa se redacteze un program care sterge din structura de arbore toate fisierele a caror dimensiune este mai mica decat o dimensiune data.

4.2. Se da un arbore binar ordonat cu chei intregi. Sa se scrie un program care determina si suprima toate nodurile arborelui care se afla initial de pe un nivel i dat, unde i nu este nivelul maxim. Ilustrati structura arborelui inainte si dupa suprimarea nodurilor.