TechCodeview

Arborele binar înseamnă că nodul poate avea maximum doi copii. Aici, numele binar însuși sugerează că „doi”; prin urmare, fiecare nod poate avea fie 0, 1 sau 2 copii.

Să înțelegem arborele binar printr-un exemplu.

Arborele de mai sus este un arbore binar, deoarece fiecare nod conține maximum doi copii. Reprezentarea logică a arborelui de mai sus este dată mai jos:

În arborele de mai sus, nodul 1 conține doi indicatori, adică un indicator stânga și unul drept care indică către nodul stâng și, respectiv, drept. Nodul 2 conţine ambele nodurile (nodul din stânga şi din dreapta); prin urmare, are două indicatori (stânga și dreapta). Nodurile 3, 5 și 6 sunt nodurile frunzelor, deci toate aceste noduri conțin NUL indicator pe ambele părți din stânga și din dreapta.

înlocuire șir de caractere javascript

Proprietățile arborelui binar

• La fiecare nivel al lui i, numărul maxim de noduri este 2ⁱ.
• Înălțimea arborelui este definită ca cea mai lungă cale de la nodul rădăcină la nodul frunză. Arborele prezentat mai sus are o înălțime egală cu 3. Prin urmare, numărul maxim de noduri la înălțimea 3 este egal cu (1+2+4+8) = 15. În general, numărul maxim de noduri posibil la înălțimea h este (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Numărul minim de noduri posibil la înălțimea h este egal cu h+1 .
• Dacă numărul de noduri este minim, atunci înălțimea arborelui ar fi maximă. În schimb, dacă numărul de noduri este maxim, atunci înălțimea arborelui ar fi minimă.

Dacă există „n” număr de noduri în arborele binar.

Înălțimea minimă poate fi calculată astfel:

După cum știm că,

n = 2^h+1-1

n+1 = 2^h+1

Luând buștean pe ambele părți,

Buturuga₂(n+1) = log2(2^h+1)

Buturuga₂(n+1) = h+1

h = jurnal₂(n+1) - 1

Înălțimea maximă poate fi calculată astfel:

După cum știm că,

n = h+1

h= n-1

Tipuri de arbore binar

Există patru tipuri de arbore binar:

Arbore binar complet/adecvat/ strict Arborele binar complet Arborele binar perfect Arbore binar degenerat Arbore binar echilibrat

1. Arbore binar complet/ propriu/ strict

Arborele binar complet este cunoscut și ca arbore binar strict. Arborele poate fi considerat arbore binar complet numai dacă fiecare nod trebuie să conțină fie 0, fie 2 copii. Arborele binar complet poate fi definit și ca arborele în care fiecare nod trebuie să conțină 2 copii, cu excepția nodurilor frunze.

Să ne uităm la exemplul simplu al arborelui binar complet.

imprimare din java

În arborele de mai sus, putem observa că fiecare nod conține fie zero, fie doi copii; prin urmare, este un arbore binar complet.

Proprietățile arborelui binar complet

• Numărul de noduri de frunză este egal cu numărul de noduri interne plus 1. În exemplul de mai sus, numărul de noduri interne este 5; prin urmare, numărul nodurilor frunzelor este egal cu 6.
• Numărul maxim de noduri este același cu numărul de noduri din arborele binar, adică 2^h+1-1.
• Numărul minim de noduri din arborele binar complet este 2*h-1.
• Înălțimea minimă a arborelui binar complet este Buturuga₂(n+1) - 1.
• Înălțimea maximă a arborelui binar complet poate fi calculată astfel:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

verificați nul în java

Arborele binar complet

Arborele binar complet este un arbore în care toate nodurile sunt complet umplute, cu excepția ultimului nivel. În ultimul nivel, toate nodurile trebuie să fie cât mai lăsate posibil. Într-un arbore binar complet, nodurile ar trebui adăugate din stânga.

Să creăm un arbore binar complet.

Arborele de mai sus este un arbore binar complet, deoarece toate nodurile sunt complet umplute, iar toate nodurile din ultimul nivel sunt adăugate mai întâi în stânga.

Proprietățile arborelui binar complet

• Numărul maxim de noduri în arborele binar complet este 2^h+1- 1.
• Numărul minim de noduri în arborele binar complet este 2^h.
• Înălțimea minimă a unui arbore binar complet este Buturuga₂(n+1) - 1.
• Înălțimea maximă a unui arbore binar complet este

Arborele binar perfect

Un arbore este un arbore binar perfect dacă toate nodurile interne au 2 copii și toate nodurile frunze sunt la același nivel.

Să ne uităm la un exemplu simplu de arbore binar perfect.

Arborele de mai jos nu este un arbore binar perfect, deoarece toate nodurile frunzelor nu sunt la același nivel.

Notă: Toți arborii binari perfecți sunt arborii binari completi, precum și arborele binar complet, dar invers nu este adevărat, adică toți arborii binari completi și arborii binari completi sunt arborii binari perfecți.

Arborele binar degenerat

Arborele binar degenerat este un arbore în care toate nodurile interne au un singur copil.

Să înțelegem arborele binar degenerat prin exemple.

Arborele de mai sus este un arbore binar degenerat deoarece toate nodurile au un singur copil. Este, de asemenea, cunoscut ca un arbore înclinat la dreapta, deoarece toate nodurile au doar un copil potrivit.

Arborele de mai sus este, de asemenea, un arbore binar degenerat, deoarece toate nodurile au un singur copil. Este, de asemenea, cunoscut ca un arbore declinat la stânga, deoarece toate nodurile au doar un copil stâng.

Arborele binar echilibrat

Arborele binar echilibrat este un arbore în care atât arborii din stânga cât și cei din dreapta diferă cu cel puțin 1. De exemplu, AVL și Copaci roșu-negri sunt arbore binar echilibrat.

Să înțelegem arborele binar echilibrat prin exemple.

Arborele de mai sus este un arbore binar echilibrat, deoarece diferența dintre subarborele din stânga și subarborele din dreapta este zero.

Arborele de mai sus nu este un arbore binar echilibrat, deoarece diferența dintre subarborele din stânga și subarborele din dreapta este mai mare de 1.

Implementarea arborelui binar

Un arbore binar este implementat cu ajutorul indicatorilor. Primul nod din arbore este reprezentat de indicatorul rădăcină. Fiecare nod din arbore este format din trei părți, adică date, indicatorul stâng și indicatorul din dreapta. Pentru a crea un arbore binar, trebuie mai întâi să creăm nodul. Vom crea nodul definit de utilizator după cum se arată mai jos:

 struct node { int data, struct node *left, *right; } 

În structura de mai sus, date este valoarea, indicatorul din stânga conține adresa nodului din stânga și indicatorul drept conţine adresa nodului drept.

Jasmine Davis în copilărie

Programul arbore binar în C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Codul de mai sus apelează recursiv funcția create() și creează un nou nod la fiecare apel recursiv. Când toate nodurile sunt create, atunci formează o structură de arbore binar. Procesul de vizitare a nodurilor este cunoscut sub denumirea de traversare a arborilor. Există trei tipuri de traversări utilizate pentru a vizita un nod:

• Parcurs în ordine
• Precomanda traversare
• Parcursul prin comanda postala