Arborele (informatică)
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În informatică , un copac sau o structură de copac ( copac în engleză ) este structura de date care duce înapoi la conceptul de copac înrădăcinat prezent în teoria graficelor . Un copac este alcătuit din două tipuri de substructuri fundamentale: nodul , care conține în general informații și arcul , care stabilește o conexiune ierarhică între două noduri: vorbim apoi despre un nod părinte din care iese un arc orientat care îl conectează către un nod copil .
De asemenea, se solicită ca fiecare nod să aibă cel mult un singur arc de intrare, în timp ce un număr diferit de arcuri de ieșire poate ieși din diferitele noduri. În cele din urmă, copacul este rugat să aibă un singur nod fără un arc de intrare: acest nod se numește rădăcina copacului. Fiecare nod care nu are arcuri de ieșire se numește nod frunză și în fiecare copac finit, adică cu un număr finit de noduri, există cel puțin un nod frunze. Evident, un nod poate fi atât părinte (dacă are margini de ieșire), cât și copil (dacă are o margine de intrare, adică dacă este diferit de rădăcină) în același timp.
De obicei, fiecare nod poartă cu sine informații și foarte des, de asemenea, o cheie cu care este posibil să o identificați în mod unic în interiorul copacului. Înălțimea sau adâncimea copacului este maximul lungimilor căilor sale maxime , căi care merg de la rădăcină la frunzele sale.
Tipuri de copaci
În principal copacii sunt împărțiți în copaci neordonați și copaci ordonați . Primii nu respectă nicio regulă în ceea ce privește relațiile părinte-copil, în timp ce cel din urmă necesită o ordonare precisă între nodul părinte și nodurile copil. Cele mai utilizate în domeniul IT sunt cu siguranță arborii ordonați . O altă clasificare se poate face pe baza numărului maxim de copii pe care un nod îl poate avea. Prin urmare, putem vorbi de copaci binari în care fiecare nod poate avea maximum doi copii sau de copaci n-ari în care nu există nicio limită la numărul maxim de noduri copil.
O caracterizare suplimentară este cea care se bazează pe așa-numita echilibrare: un copac este perfect echilibrat dacă are toate frunzele la același nivel, adică dacă fiecare frunză a arborelui are aceeași distanță de rădăcină. Un copac este - echilibrat dacă, pentru fiecare nod N , numit K setul de niveluri maxime care pot fi atinse urmărind toate frunzele lui N , diferența dintre maxim și minim de K nu este mai mare de .
Setul de noduri de deasupra unui nod compune setul de predecesori, următorii sunt descendenții.
Cele mai frecvente tipuri de copaci sunt următoarele:
- Arborele binar
- Căutați arborele binar , numit și BST
- Arborele 2-3
- 2-3-4 copac
- Copac AVL
- Morman
- RB-Ax
- Arborele B
- Arborele cadramentului
- Arborele octal
Implementări
Cea mai obișnuită implementare a copacilor se bazează pe liste legate , adică de obiecte (noduri) care se referă la alte obiecte.
Java
O interfață tipică a unui nod al unui arbore binar în Java poate fi următoarea:
public class Node {
nodul public stâng copil ;
nodul public dreapta copil ;
// informațiile conținute de nod, de tipul Obiect de generalizat
informații despre obiecte publice ;
// o cheie unică pentru identificarea nodului, de exemplu un număr întreg
public int uniquekey ;
}
Notoriu, copacii de grămadă sunt, de asemenea, implementabili prin tablouri sau vectori
C.
- Definirea structurii
typedef int TKey ;
typedef int TSat ;
struct SInfo {
Tastă cheie ;
Satelit TSAT;
};
typedef struct SInfo TInfo ;
struct SNode {
TInfo info ;
struct SNode * stânga ;
struct SNode * dreapta ;
};
typedef struct SNode TNode ;
typedef TNode * TTree ;
- Crearea copacilor
TTree tree_create () {
return NULL ;
}
- Distrugerea copacilor
TTree tree_destroy ( arbore TTree ) {
if ( tree_empty ( tree ) == true )
return NULL ;
else if (( copac -> stânga == NULL ) && ( copac -> dreapta == NUL )) {
liber ( copac );
return NULL ;
} altceva {
copac -> stânga = distrugere_arbor ( copac -> stânga );
copac -> dreapta = copac_distruge ( copac -> dreapta );
liber ( copac );
return NULL ;
}
}
- Căutați elementul
TNode * tree_search_recursive ( TTree tree , TKey key ) {
if (( tree_empty ( tree ) == true ) || egal ( copac -> info . cheie , cheie ))
copac de întoarcere ;
altceva {
if ( mai mare ( cheie , copac -> informație . cheie ))
returnează căutare_recursiv copac ( copac -> dreapta , cheie );
altceva
returnează căutare_recursiv copac ( copac -> stânga , cheie );
}
}
- Introduceți elementul
TTree tree_insert_recursive ( TTree tree , TInfo info ) {
if ( tree_empty ( tree ) == true ) {
TNode * newnode ;
newnode = ( TNode * ) malloc ( sizeof ( TNode ));
if ( newnode == NULL ) {
printf ( „Eroare de alocare” );
ieșire ( 1 );
}
newnode -> dreapta = newnode -> left = NULL ;
newnode -> info = info ;
returnează noul nod ;
} else if ( ! greater ( info . key , tree -> info . key )) {
copac -> stânga = copac_insert_recursiv ( copac -> stânga , informații );
copac de întoarcere ;
} altceva {
copac -> dreapta = copac_insert_recursiv ( copac -> dreapta , informații );
copac de întoarcere ;
}
}
- Sterge articolul
TTree tree_delete_ver2 ( TTree tree , TKey key ) {
if ( tree_empty ( tree ) == true ) / * Arborele gol * /
return NULL ;
else if ( mai mare ( copac -> info . cheie , cheie )) {
/ * Anulare în ramura din stânga * /
copac -> stânga = copac_delete_ver2 ( copac -> stânga , cheie );
copac de întoarcere ;
}
else if ( mai mare ( key , tree -> info . key )) {
/ * Anulare în ramura dreaptă * /
copac -> dreapta = copac_delete_ver2 ( copac -> dreapta , cheie );
copac de întoarcere ;
} else { /*tree->info.key==key * /
/ * Ștergerea rădăcinii * /
TNode * min_right , * alias ;
if ( tree_empty ( tree -> right ) == true )
alias = copac -> stânga ;
altceva {
min_right = tree_min ( copac -> dreapta );
min_right -> left = tree -> left ;
alias = copac -> dreapta ;
}
liber ( copac );
return alias ;
}
}
Vizita copacilor adânci
Mulți algoritmi care operează pe copaci necesită să vizitați toate nodurile arborelui sau să definiți un (sub) algoritm care, având în vedere un copac, construiește permutarea setului de noduri ale acestuia. Metodele de examinare aprofundată sunt următoarele.
- Vizitați în precomandă : rădăcina este vizitată mai întâi, după subarborele din stânga și, în final, subarborele din dreapta
void visitapreorder ( pornire Nodepointer )
{
if ( start == NULL ) return ;
start -> markup = 1 ;
printf ( " % d % d \ n " , start -> valoare , start -> markup );
visitapreorder ( start -> son_sx );
visitapreorder ( start -> son_dx );
}
Nodepointer este un indicator către nodul rădăcină de la care începe căutarea de precomandă. son_sx și son_dx sunt respectiv copiii din stânga și din dreapta nodului de la care începe căutarea. Algoritmul descris se limitează la imprimarea valorii și marcajului nodului considerat pe ecran.
- Vizitați în ordine : se vizitează mai întâi subarborele din stânga, apoi rădăcina și, în final, subarborele din dreapta
void visiteinorder ( pornire Nodepointer )
{
if ( start == NULL ) return ;
visitinorder ( start -> son_sx );
start -> markup = 1 ;
printf ( " % d % d \ n " , start -> valoare , start -> markup );
visitinorder ( start -> son_dx );
}
Nodepointer este un indicator către nodul rădăcină de la care începe căutarea în ordine. son_sx și son_dx sunt respectiv copiii din stânga și din dreapta nodului de la care începe căutarea. Algoritmul descris se limitează la imprimarea valorii și marcajului nodului considerat pe ecran.
- Vizită după comandă : se vizitează mai întâi subarborele din stânga, apoi subarborele din dreapta și, în final, rădăcina
void visitapostorder ( Nodepointer start )
{
if ( start == NULL ) return ;
visitapostorder ( start -> son_sx );
visitapostorder ( start -> son_dx );
start -> markup = 1 ;
printf ( " % d % d \ n " , start -> valoare , start -> markup );
}
Nodepointer este un indicator către nodul rădăcină de la care începe căutarea după comandă. son_sx și son_dx sunt respectiv copiii din stânga și din dreapta nodului de la care începe căutarea. Algoritmul descris se limitează la imprimarea valorii și marcajului nodului considerat pe ecran.
Fiecare metodă poate fi aplicată recursiv , adică prin „vizită la un subarborescent” ne referim la aplicarea aceluiași algoritm pentru a vizita nodul rădăcină al acelui subarborod. Alternativ, este posibil să implementați vizita în profunzime folosind o baterie .
Un exemplu de metodă exclusiv non - recursiv pe un copac este dat de vizita în lățime .
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere de copac
linkuri externe
- ( EN ) Tree , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
