Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Satisfactia de a face ce iti place. tutorial, lectii online, solutii simple, exmeple, programe, C++

Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

C


Index » educatie » » informatica » C
Arbori - Reprezentare. Cautare. Inserare. Parcurgere. Stergere.


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.

1. 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

}

}

}

2. 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

}

}

}



C


Access
Adobe photoshop
Autocad
Baze de date
C
Calculatoare
Corel draw
Excel
Foxpro
Html
Internet
Java
Linux
Mathcad
Matlab
Outlook
Pascal
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word

Functii operator membre ale claselor
Supraincarcarea operatorilor
EXPRESII SI INSTRUCTIUNI
Supraincarcarea functiilor
DECLARATII SI CONSTANTE
Controale orientate spre intervale de valori
CLASE
Destructori
OPERATOR SUPRAINCARCAT
Evidenta bauturilor dintr-o crama. Aplicatia se va realiza in limbajul C folosind fisiere text si fisiere binare.

















 
Copyright © 2014 - Toate drepturile rezervate