Arbori - Reprezentare. Cautare. Inserare. Parcurgere. Stergere.

Arbori - Reprezentare. Cautare. Inserare. Parcurgere. Stergere.

• Un arbore consta din noduri care sunt unite prin muchii.
• Singurul mod de a ajunge de la un nod la altul este de a urma un drum de-a lungul muchiilor.
• Cale (drum) - ne deplasam de la un nod la altul de-a lungul muchiilor prin care acestea sunt conectate; secventa de noduri rezultata se numeste cale.
• Radacina - nodul din varful arborelui.
• Parinte - orice nod (cu exceptia radacinii) are exact o muchie orientata in sus spre un alt nod. Nodul situat mai sus este numit parintele nodului curent.
• Fiu - orice nod poate avea una sau mai multe muchii orientate in jos, spre alte noduri. Aceste noduri situate mai jos sunt numite fii nodului curent.
• Frunza - un nod fara fii.
• Subarbore - un nod poate fi considerat ca radacina pentru un subarbore, care cuprinde fii acelui nod, fii fiilor sai etc (pana se ajunge la frunze).
• Vizitare - un nod este vizitat atunci cand se executa operatii asupra sa; o simpla trecere printr-un nod cu scopul de ajunge al alt nod nu este considerata vizitare.
• Parcurgere - vizitarea tuturor nodurilor din arbore.

parcurgere in inordine (subarbore stang - radacina - subarbore drept)

parcurgere in preordine (radacina - subarbore stang - subarbore drept)

parcurgere in postordine (subarbore stang - subarbore drept - radacina)

• Nivel - nivelul unui nod este numarul de muchii parcurse pentru a ajunge de la radacina la acel nod. Radacina arborelui este pe nivelul 0, fii acesteia pe nivelul 1 etc.
• Cheie - valoarea nodului.
• Arbore binar - un arbore in care orice nod poate avea cel mult doi fii.
• Arbori neechilibrati - radacina are mai multi descendenti stangi decat drepti sau invers.
• Arbore binar de cautare - toate nodurile care sunt descendentii stangi ai unui nod X au chei mai mici decat X; toate nodurile care sunt descendentii drepti ai unui nod X au chei mai mari decat X.    In acest caz, parcurgerea in inordine realizeaza parcurgerea nodurilor in ordine crescatoare a cheilor.

• Arbore 2-3-4 - este un arbore echilibrat care poate contine trei tipuri de noduri: 2-noduri care au o cheie si 2 fii, 3-noduri care au 2 chei si 3 fii si 4-noduri care au 3 chei si 4 fii.

Sa se implementeze urmatoarele operatii pentru un arbore binar de cautare:

- inserare nod;

- stergere nod;

- parcurgere in inordine;

- parcurgere in postordine;

- parcurgere in preordine.

import java.io.*;

class Nod

class Arbore

//metoda de cautare

public Nod cauta(int n)

return curent;

}

//metoda inserare nod nou

public void insereaza(int n)

}

else //deplasare la dreapta?

}

}

}

}

//metoda stergere nod

public boolean sterge(int n)

else

if(curent==null) //nu s-a gasit cheia

return false;

}

//am gasit nodul care trebuie sters

//daca nodul nu are copii se sterge direct

if((curent.st==null)&&(curent.dr==null))

//nodul de sters are un fiu

//daca nu exista fiu in dreapta, se inlocuieste cu subarborele stang

else

if(curent.dr==null)

if(curent==radacina)

radacina=curent.st;

else

if(t)

parinte.st=curent.st;

else

parinte.dr=curent.st;

//daca nu exista fiu in stanga, inlocuieste cu subarborele drept

else

if(curent.st==null)

if(curent==radacina)

radacina=curent.dr;

else

if(t)

parinte.st=curent.dr;

else

parinte.dr=curent.dr;

//dc nodul are 2 fii, atunci se inlocuieste cu succesorul inordine

else

//succesor nu poate avea subarbore stang

return true;

}

//intoarce nodul cu valoarea imediat mai mare decat valoarea de sters

//parcurge fiul drept apoi descendentii din stanga

private Nod cautaSuccesor(Nod nd)

//daca succesorul nu e fiul drept modifica referintele

if(succesor!=nd.dr)

return succesor;

}

//metoda de parcurgere

public void parcurge(int opt)

System.out.println();

}

//parcurgere in preordine

public void preordine(Nod m)

}

//parcurgere in inordine

public void inordine(Nod m)

}

//parcurgere in postordine

public void postordine(Nod m)

}

}

class arbori

// introducere integer

public static int getInt() throws IOException

public static void main(String[] args) throws IOException

Sa se implementeze urmatoarele operatii pentru un arbore 2-3-4:

- inserare nod;

- cautare valoare;

- afisare arbore.

import java.io.*;

class Cheie

//afisare element

public void afisareValoare()

class Nod

//deconecteaza fiul de la acest nod

public Nod deconectareFiu(int numarFiu)

public Nod returneazaFiu(int numarFiu)

public Nod returneazaParinte()

public boolean esteFrunza()

public int returneazaNumarChei()

//intoarce valoarea de pe pozitia x

public Cheie returneazaCheie(int x)

public boolean estePlin()

//intoarce indicele elementului care are o anumita valoare

public int cautaValoare(int info)

return -1; //daca nu gaseste elementul intoarce -1

}

//adauga valoare la un nod

public int adaugaCheie(Cheie cheieNoua)

}

}

cheiVect[0]=cheieNoua;

return 0;

}

//sterge elementul maxim din nod

public Cheie stergeCheie()

//afisare nod

public void afiseazaNod()

class Arbore234

}

//intoarce fiul corespunzator al nodului in cautaea valorii

public Nod fiuUrmator(Nod nodCurent, int val)

//daca valoarea este mai mare returneaza ultimul fiu

return nodCurent.returneazaFiu(i);

}

//metoda inserare cheie

public void insereaza(int val)

else

if (nodCurent.esteFrunza())

break;

else

//nodul nu este nici complet, nici frunza

//avanseaza la nivelul urmator

nodCurent=fiuUrmator(nodCurent,val);

}

nodCurent.adaugaCheie(tempCheie);

}

//metoda de divizare

public void divizeaza(Nod nodCurent)

else

parinte=nodCurent.returneazaParinte();

nr=parinte.adaugaCheie(cheie2);

int n=parinte.returneazaNumarChei();

for (int i=n-1; i>nr; i--)

parinte.conectareFiu(nr+1,nodNou);

//conecteaza nodNou cu parintele

nodNou.adaugaCheie(cheie3);

nodNou.conectareFiu(0,fiu2);

nodNou.conectareFiu(1,fiu3);

}

public void afisareArbore()

private void afisareRecursivaArbore(Nod nodCurent,int nivel,int nrFiu)

}

class arbori234Aplicatie

// introducere integer

public static int getInt() throws IOException

public static void main(String[] args) throws IOException

}

}