Meniu

Structura de date a arborelui binar în C ++

binary tree data structure c

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial aprofundat despre arborele binar în C ++ explică tipurile, reprezentarea, traversarea, aplicațiile și implementarea arborilor binari în C ++:

Un arbore binar este o structură de date a copacului utilizată pe scară largă. Când fiecare nod al unui copac are cel mult două noduri copil, atunci arborele este numit arbore binar.

Deci, un arbore binar tipic va avea următoarele componente:

  • Un subarbore stâng
  • Un nod rădăcină
  • Un subarborel drept

=> Urmăriți lista completă a tutorialelor C ++ din această serie.

Arborele binar în C ++

Ce veți învăța:

Arborele binar în C ++

O reprezentare picturală a unui arbore binar este prezentată mai jos:

Reprezentarea pictorială a unui arbore binar

Într-un arbore binar dat, numărul maxim de noduri la orice nivel este 2l-1unde „l” este numărul de nivel.

Astfel, în cazul nodului rădăcină la nivelul 1, numărul maxim de noduri = 21-1= 20= 1

Deoarece fiecare nod dintr-un arbore binar are cel mult două noduri, nodurile maxime la nivelul următor vor fi, 2 * 2l-1.

ceea ce vedeți este ceea ce obțineți constructor de site-uri web

Dat fiind un copac binar de adâncime sau înălțime de h, numărul maxim de noduri dintr-un copac binar de înălțime h = 2h- 1.

Prin urmare, într-un copac binar de înălțime 3 (prezentat mai sus), numărul maxim de noduri = 23-1 = 7.

Acum, să discutăm diferitele tipuri de arbori binari.

Tipuri de arbori binari

Următoarele sunt cele mai comune tipuri de arbori binari.

# 1) Arborele binar complet

Un copac binar în care fiecare nod are 0 sau 2 copii este denumit ca un copac binar complet.

Arborele binar complet

Arătat mai sus este un copac binar complet în care putem vedea că toate nodurile sale, cu excepția nodurilor frunzei, au doi copii. Dacă L este numărul de noduri frunze și „l” este numărul de noduri interne sau non-frunze, atunci pentru un arbore binar complet, L = l + 1.

# 2) Arborele binar complet

Un arbore binar complet are toate nivelurile umplute, cu excepția ultimului nivel, iar ultimul nivel are toate nodurile la fel de mult ca în stânga.

Arborele binar complet

Arborele prezentat mai sus este un arbore binar complet. Un exemplu tipic de arbore binar complet este o grămadă binară pe care o vom discuta în tutorialele ulterioare.

# 3) Arborele binar perfect

Un copac binar este numit perfect atunci când toate nodurile sale interne au doi copii și toate nodurile frunzei sunt la același nivel.

Arborele binar perfect

Un exemplu de arbore binar prezentat mai sus este un arbore binar perfect deoarece fiecare dintre nodurile sale are doi copii și toate nodurile frunzelor sunt la același nivel.

Un arbore binar perfect de înălțime h are 2h- 1 număr de noduri.

# 4) Un copac degenerat

Un copac binar în care fiecare nod intern are un singur copil se numește copac degenerat.

Un copac degenerat

Arborele prezentat mai sus este un copac degenerat. În ceea ce privește performanța acestui arbore, arborii degenerați sunt identici cu listele legate.

# 5) Arborele binar echilibrat

Un copac binar în care adâncimea celor două subarburi ale fiecărui nod nu diferă niciodată cu mai mult de 1 se numește copac binar echilibrat.

Arborele binar echilibrat

Arborele binar prezentat mai sus este un arbore binar echilibrat, deoarece adâncimea celor două subarburi ale fiecărui nod nu depășește 1. Arborii AVL despre care vom discuta în tutorialele noastre ulterioare sunt un arbore echilibrat comun.

Reprezentarea binară a arborelui

Un arbore binar este alocat de memorie în două moduri.

# 1) Reprezentare secvențială

Aceasta este cea mai simplă tehnică de stocare a unei structuri de date în arbore. O matrice este utilizată pentru a stoca nodurile arborelui. Numărul de noduri dintr-un copac definește dimensiunea matricei. Nodul rădăcină al arborelui este stocat la primul index din matrice.

ce este un fișier 7z?

În general, dacă un nod este stocat la ialocația este apoi stânga și dreapta copilul este stocat la 2i și respectiv 2i + 1 locație.

Luați în considerare următorul arbore binar.

Exemplu de arbore binar

Reprezentarea secvențială a arborelui binar de mai sus este următoarea:

reprezentarea secvențială a arborelui binar

În reprezentarea de mai sus, vedem că copilul din stânga și din dreapta fiecărui nod este stocat la locațiile 2 * (node_location) și 2 * (node_location) +1 respectiv.

De exemplu, locația nodului 3 din matrice este 3. Deci, copilul din stânga va fi plasat la 2 * 3 = 6. Fiul său din dreapta va fi la locația 2 * 3 +1 = 7. După cum putem vedea în matrice, copiii din 3 care sunt 6 și 7 sunt plasate la locația 6 și 7 din matrice.

Reprezentarea secvențială a arborelui este ineficientă, deoarece matricea utilizată pentru a stoca nodurile arborelui ocupă mult spațiu în memorie. Pe măsură ce arborele crește, această reprezentare devine ineficientă și dificil de gestionat.

Acest dezavantaj este depășit prin stocarea nodurilor de copac într-o listă legată. Rețineți că, dacă arborele este gol, atunci prima locație care stochează nodul rădăcină va fi setată la 0.

# 2) Reprezentare pe listă legată

În acest tip de reprezentare, o listă legată este utilizată pentru a stoca nodurile arborelui. Mai multe noduri sunt împrăștiate în memorie în locații non-contigue și nodurile sunt conectate folosind relația părinte-copil ca un copac.

Următoarea diagramă arată o reprezentare a listei legate pentru un arbore.

Reprezentare pe listă legată

Așa cum se arată în reprezentarea de mai sus, fiecare nod de listă legată are trei componente:

  • Indicatorul stâng
  • Partea de date
  • Pointer dreapta

Pointerul stâng are un pointer către copilul stâng al nodului; indicatorul drept are un indicator către copilul drept al nodului, în timp ce partea de date conține datele reale ale nodului. Dacă nu există copii pentru un nod dat (nodul frunzei), atunci indicatoarele stânga și dreapta pentru acel nod sunt setate la nul așa cum se arată în figura de mai sus.

Implementarea arborelui binar în C ++

Apoi, dezvoltăm un program arbore binar folosind o reprezentare listă legată în C ++. Folosim o structură pentru a declara un singur nod și apoi folosind o clasă, dezvoltăm o listă legată de noduri.

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Ieșire:

Arborele binar creat:

5 10 15 20 30 40 45

Transversarea arborelui binar

Am discutat deja traversări în tutorialul nostru de bază despre copaci. În această secțiune, permiteți-ne să implementăm un program care introduce noduri în arborele binar și demonstrează, de asemenea, toate cele trei traversări, adică inorder, preorder și postorder, pentru un arbore binar.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Ieșire:

Trecere în ordine:

A B C D E F G

Trecerea comenzii prin poștă:

G F E D C B A

Traversare precomandă:

A B C D E F G

Aplicații ale arborelui binar

Un arbore binar este utilizat în multe aplicații pentru stocarea datelor.

Unele dintre aplicațiile importante ale copacilor binari sunt enumerate mai jos:

  • Arborii de căutare binari: Arborii binari sunt folosiți pentru a construi un arbore de căutare binar care este utilizat în multe aplicații de căutare, cum ar fi seturi și hărți, în multe biblioteci de limbi.
  • Copaci Hash: Folosit pentru verificarea hashurilor în principal în aplicații specializate de semnare a imaginilor.
  • Grămezi: Heap-urile sunt utilizate pentru implementarea cozilor prioritare care sunt utilizate pentru routere, programarea procesorilor în sistemul de operare etc.
  • Codificare Huffman: Arborele de codare Huffman este utilizat în algoritmi de compresie (cum ar fi compresia imaginii), precum și în aplicații criptografice.
  • Arborele de sintaxă: Compilatoarele construiesc adesea arbori de sintaxă care nu sunt altceva decât arbori binari pentru a analiza expresiile utilizate în program.

Concluzie

Arborii binari sunt structuri de date utilizate pe scară largă în întreaga industrie software. Arborii binari sunt copacii ale căror noduri au cel mult două noduri copil. Am văzut diferite tipuri de arbori binari, cum ar fi un copac binar complet, un copac binar complet, un copac binar perfect, un copac binar degenerat, un copac binar echilibrat etc.

Datele arborelui binar pot fi, de asemenea, parcurse folosind tehnici de trecere inorder, preorder și postorder pe care le-am văzut în tutorialul nostru anterior. În memorie, un arbore binar poate fi reprezentat folosind o listă legată (memorie necontiguă) sau tablouri (reprezentare secvențială).

Reprezentarea listelor legate este mai eficientă în comparație cu matricele, deoarece matricele ocupă mult spațiu.

=> Consultați aici cele mai bune tutoriale de formare C ++.

Lectură recomandată

^