Meniu

Copaci în C ++: terminologie de bază, tehnici transversale și tipuri de arbori C ++

  • Principal
  • Alte
  • Copaci în C ++: terminologie de bază, tehnici transversale și tipuri de arbori C ++

trees c basic terminology

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial detaliat despre copacii C ++ explică tipurile de arbori, tehnicile de traversare a arborilor și terminologia de bază cu imagini și exemple de programe:

În această serie C ++, până acum am văzut structura liniară a datelor atât de natură statică, cât și dinamică. Acum vom continua cu structura de date neliniară. Prima structură de date din această categorie este „Copaci”.

Arborii sunt structuri de date ierarhice neliniare. Un copac este o colecție de noduri conectate între ele prin intermediul „muchiilor” care sunt fie direcționate, fie nedirecționate. Unul dintre noduri este desemnat ca „nod rădăcină”, iar nodurile rămase sunt numite noduri copil sau nodurile frunze ale nodului rădăcină.

În general, fiecare nod poate avea cât mai mulți copii, dar numai un nod părinte.

=> Verificați întreaga serie de formare C ++

Arborele în C ++

Nodurile unui copac sunt fie la același nivel numite noduri surori, fie pot avea o relație părinte-copil. Nodurile cu același părinte sunt noduri frate.

Ce veți învăța:

Copaci în C ++

Dat mai jos este un exemplu de copac cu diferitele sale părți.

Arborele în C ++ cu diferitele sale părți

Să parcurgem definițiile unor termeni de bază pe care îi folosim pentru copaci.

  • Nodul rădăcină: Acesta este cel mai de sus nod din ierarhia arborelui. În diagrama de mai sus, nodul A este nodul rădăcină. Rețineți că nodul rădăcină nu are părinte.
  • Nodul frunzei: Este cel mai de jos nod dintr-o ierarhie arborescentă. Nodurile frunze sunt nodurile care nu au noduri copil. Ele sunt, de asemenea, cunoscute sub numele de noduri externe. Nodurile E, F, G, H și C din arborele de mai sus sunt toate noduri frunze.
  • Subarbore: Subarborele reprezintă diferiți descendenți ai unui nod atunci când rădăcina nu este nulă. Un copac constă de obicei dintr-un nod rădăcină și unul sau mai mulți subarburi. În diagrama de mai sus, (B-E, B-F) și (D-G, D-H) sunt subarburi.
  • Nodul părinte: Orice nod, cu excepția nodului rădăcină, care are un nod copil și o margine în sus către părinte.
  • Nod strămoș: Este orice nod predecesor pe o cale de la rădăcină la acel nod. Rețineți că rădăcina nu are strămoși. În diagrama de mai sus, A și B sunt strămoșii lui E.
  • Cheie: Reprezintă valoarea unui nod.
  • Nivel: Reprezintă generarea unui nod. Un nod rădăcină este întotdeauna la nivelul 1. Nodurile copil ale rădăcinii sunt la nivelul 2, nepoții rădăcinii sunt la nivelul 3 și așa mai departe. În general, fiecare nod este la un nivel mai înalt decât părintele său.
  • Cale: Calea este o secvență de margini consecutive. În diagrama de mai sus, calea către E este A => B-> E.
  • Grad: Gradul unui nod indică numărul de copii pe care îi are un nod. În diagrama de mai sus, gradul lui B și D este 2 fiecare, în timp ce gradul lui C este 0.

Tipuri de arbori C ++

Structura datelor arborelui poate fi clasificată în următoarele subtipuri, după cum se arată în diagrama de mai jos.

cum se fac fișiere .jar deschise cu java

Tipuri de copaci în C ++

# 1) Arborele general

Arborele general este reprezentarea de bază a unui copac. Are un nod și unul sau mai multe noduri copil. Nodul de nivel superior, adică nodul rădăcină este prezent la nivelul 1 și toate celelalte noduri pot fi prezente la diferite niveluri.

Un arbore general este prezentat în figura de mai jos.

Arborele general

Așa cum se arată în figura de mai sus, un arbore general poate conține orice număr de subarburi. Nodurile B, C și D sunt prezente la nivelul 2 și sunt noduri frate. În mod similar, nodurile E, F, G și H sunt și noduri frate.

Nodurile prezente la diferite niveluri pot prezenta o relație părinte-copil. În figura de mai sus, nodurile B, C și D sunt copiii lui A. Nodurile E și F sunt copiii lui B, în timp ce nodurile G și H sunt copiii lui D.

Arborele general este demonstrat mai jos folosind implementarea C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Ieșire:

Arborele general creat este după cum urmează:

10

/

20 30

/

40

# 2) Păduri

Ori de câte ori ștergem nodul rădăcină din copac și marginile care unesc elementele de nivel următor și rădăcină, obținem seturi de copaci disjunși așa cum se arată mai jos.

Păduri

În figura de mai sus, am obținut două păduri prin ștergerea nodului rădăcină A și a celor trei margini care conectau nodul rădăcină la nodurile B, C și D.

# 3) Arborele binar

O structură de date de copac în care fiecare nod are cel mult două noduri copil se numește copac binar. Un copac binar este cea mai populară structură de date a copacului și este utilizat într-o serie de aplicații precum evaluarea expresiei, baze de date etc.

Următoarea figură arată un arbore binar.

Arborele binar

În figura de mai sus, vedem că nodurile A, B și D au fiecare doi copii. Un copac binar în care fiecare nod are exact zero sau doi copii se numește copac binar complet. În acest arbore, nu există noduri care să aibă un singur copil.

Un copac binar complet are un copac binar care este complet umplut cu excepția celui mai scăzut nivel care este umplut de la stânga la dreapta. Arborele binar prezentat mai sus este un arbore binar complet.

Următorul este un program simplu pentru a demonstra un arbore binar. Rețineți că ieșirea arborelui este secvența de traversare în ordine a arborelui de intrare.

#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:

întrebări și răspunsuri la interviu pentru asigurarea calității pdf

Arborele binar creat:

5 10 15 20 30 40 45

# 4) Arborele de căutare binar

Arborele binar care este comandat se numește arborele binar de căutare. Într-un arbore de căutare binar, nodurile din stânga sunt mai mici decât nodul rădăcină, în timp ce nodurile din dreapta sunt mai mari sau egale cu nodul rădăcină.

Un exemplu de arbore de căutare binar este prezentat mai jos.

Arborele de căutare binar

În figura de mai sus, putem vedea că nodurile din stânga sunt toate mai mici de 20, care este elementul rădăcină. Nodurile din dreapta, pe de altă parte, sunt mai mari decât nodul rădăcină. Arborele de căutare binar este utilizat în tehnici de căutare și sortare.

# 5) Arborele expresiei

Un copac binar care este utilizat pentru a evalua expresii aritmetice simple se numește copac de expresie.

Un arbore simplu de expresie este prezentat mai jos.

Arborele expresiei

În arborele de expresie de mai sus, reprezentăm expresia (a + b) / (a-b). Așa cum se arată în figura de mai sus, nodurile non-frunze ale arborelui reprezintă operatorii expresiei în timp ce nodurile frunzei reprezintă operanzii.

Arborii de expresie sunt folosiți în principal pentru rezolvarea expresiilor algebrice.

Tehnici de traversare a copacilor

Am văzut structuri de date liniare, cum ar fi tablouri, liste legate, stive, cozi, etc. Toate aceste structuri de date au o tehnică de traversare comună care traversează structura doar într-un mod, adică liniar.

Dar în cazul copacilor, avem diferite tehnici de traversare, așa cum sunt enumerate mai jos:

# 1) În ordine: În această tehnică de traversare, parcurgem mai întâi subarborele stâng până când nu mai există noduri în subarborele stâng. După aceasta, vizităm nodul rădăcină și apoi procedăm la traversarea subarborelui drept până când nu mai există noduri de traversat în subarborele drept. Astfel ordinea traversării în ordinea este stânga-> rădăcină-> dreapta.

# 2) Precomandați: Pentru tehnica de traversare a comenzii, procesăm nodul rădăcină mai întâi, apoi traversăm întreg subarborele stâng și, în cele din urmă, traversăm subarborele drept. Prin urmare, ordinea traversării preordinei este rădăcină-> stânga-> dreapta.

# 3) Post-comandă: În tehnica de traversare post-comandă, traversăm subarborele stâng, apoi subarborele drept și în final nodul rădăcină. Ordinea de traversare pentru tehnica postordine este stânga-> dreapta-> rădăcină.

Dacă n este nodul rădăcină și „l” și „r” sunt noduri stânga și respectiv dreapta ale arborelui, atunci algoritmii de traversare a arborelui sunt după cum urmează:

În ordine (lnr) algoritm:

  1. Treceți subarborele din stânga folosind inOrder (stânga- Subarborele).
  2. Accesați nodul rădăcină (n).
  3. Traversați subarborele drept folosind inOrder (dreapta- subarborele).

Algoritm de precomandă (nlr):

  1. Accesați nodul rădăcină (n).
  2. Treceți subarborele din stânga folosind pre-comanda (stânga-subarborele).
  3. Parcurgeți subarborele din dreapta folosind precomanda (dreapta-subarborele).

Algoritm postorder (lrn):

  1. Treceți subarborele din stânga utilizând postOrder (stânga-subarborele).
  2. Parcurgeți subarborele din dreapta folosind postOrder (dreapta-subarborele).
  3. Accesați nodul rădăcină (n).

Din algoritmii de mai sus ai tehnicilor de traversare, vedem că tehnicile pot fi aplicate unui copac dat într-un mod recursiv pentru a obține rezultatul dorit.

Luați în considerare următorul arbore.

internetul obiectelor pe care companiile să le urmărească

Algoritm postorder (lrn)

Folosind tehnicile de traversare de mai sus, secvența de traversare pentru arborele de mai sus este dată mai jos:

  1. Traversare în comandă: 2 3 5 6 10
  2. Traversare pre-comandă: 6 3 2 5 10
  3. Traversare PostOrder: 2 5 3 10 6

Concluzie

Arborii sunt o structură de date ierarhică neliniară care este utilizată în multe aplicații din domeniul software.

Spre deosebire de structurile de date liniare care au o singură modalitate de a traversa lista, putem traversa copacii într-o varietate de moduri. În acest tutorial am avut un studiu detaliat al tehnicilor de traversare și al diferitelor tipuri de copaci.

=> Consultați aici ghidul pentru începători C ++

Lectură recomandată

^