Menu

Træer i C ++: grundlæggende terminologi, gennemgange og C ++ trætyper

  • Vigtigste
  • Andet
  • Træer i C ++: grundlæggende terminologi, gennemgange og C ++ trætyper

trees c basic terminology

Prøv Vores Instrument Til At Fjerne Problemer

Denne dybdegående tutorial om C ++ træer forklarer trætyper, træovergange og grundlæggende terminologi med billeder og eksempelprogrammer:

I denne C ++ - serie har vi hidtil set den lineære datastruktur af både statisk og dynamisk karakter. Nu fortsætter vi med den ikke-lineære datastruktur. Den første datastruktur i denne kategori er 'Trees'.

Træer er ikke-lineære hierarkiske datastrukturer. Et træ er en samling noder, der er forbundet med hinanden ved hjælp af 'kanter', som enten er rettet eller ikke-rettet. En af knudepunkterne er betegnet som “rodknude”, og de resterende knudepunkter kaldes underknudepunkter eller bladknudepunkterne for rodknudepunktet.

hvad er den bedste vr app

Generelt kan hver knude have så mange børn, men kun en forældreknude.

=> Tjek hele C ++ træningsserien

Træ i C ++

Knudepunkter på et træ kaldes enten på samme niveau som søsterknudepunkter, eller de kan have et forhold mellem forældre og barn. Noder med samme forælder er søskendeknuder.

Hvad du lærer:

Træer i C ++

Nedenfor er et eksempel på et træ med dets forskellige dele.

Træ i C ++ med dets forskellige dele

Lad os gennemgå definitionerne af nogle grundlæggende termer, som vi bruger til træer.

  • Rodknude: Dette er den øverste knude i træhierarkiet. I ovenstående diagram er node A rodnoden. Bemærk, at rodknudepunktet ikke har nogen forælder.
  • Bladknude: Det er den nederste mest knude i et træhierarki. Bladknudepunkter er de knudepunkter, der ikke har nogen underknudepunkter. De er også kendt som eksterne noder. Knudepunkter E, F, G, H og C i ovenstående træ er alle bladknuder.
  • Undertræ: Subtræ repræsenterer forskellige efterkommere af en node, når roden ikke er nul. Et træ består normalt af en rodknude og et eller flere undertræer. I ovenstående diagram er (B-E, B-F) og (D-G, D-H) undertrær.
  • Overordnet knude: Enhver node undtagen rodnoden, der har en undernode og en kant opad mod forælderen.
  • Ancestor Node: Det er enhver forgængerknude på en sti fra roden til den knude. Bemærk, at roden ikke har nogen forfædre. I ovenstående diagram er A og B forfædrene til E.
  • Nøgle: Det repræsenterer værdien af ​​en node.
  • Niveau: Repræsenterer genereringen af ​​en node. En rodknude er altid på niveau 1. Børneknudepunkter på roden er på niveau 2, børnebørn af roden er på niveau 3 og så videre. Generelt er hver knude på et niveau højere end dens overordnede.
  • Sti: Stien er en sekvens af fortløbende kanter. I ovenstående diagram er stien til E A => B-> E.
  • Grad: Grad af en node angiver antallet af børn, som en node har. I ovenstående diagram er graden af ​​B og D hver 2, mens graden af ​​C er 0.

Typer af C ++ træer

Trædatastrukturen kan klassificeres i følgende undertyper som vist i nedenstående diagram.

Typer af træ i C ++

# 1) Generelt træ

Det generelle træ er den grundlæggende repræsentation af et træ. Det har en node og en eller flere underordnede noder. Toppeniveaunoden, dvs. rodnoden er til stede på niveau 1, og alle de andre noder kan være til stede på forskellige niveauer.

Et generelt træ er vist i nedenstående figur.

Generelt træ

Som vist i ovenstående figur kan et generelt træ indeholde et hvilket som helst antal undertræer. Knudepunkterne B, C og D er til stede på niveau 2 og er søskendeknuder. Tilsvarende er knudepunkter E, F, G og H også søskendeknuder.

Knudepunkterne på forskellige niveauer kan udvise et forhold mellem forældre og barn. I ovenstående figur er knudepunkter B, C og D børn af A. Knudepunkter E og F er børn af B, mens knudepunkter G og H er børn af D.

Det generelle træ vises nedenfor ved hjælp af C ++ implementeringen:

#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; }

Produktion:

Generelt træ oprettet er som følger:

10

/

20 30

/

40

# 2) Skove

Hver gang vi sletter rodknudepunktet fra træet og kanterne, der forbinder de næste niveauelementer og roden, får vi uensartede sæt træer som vist nedenfor.

Skove

I ovenstående figur opnåede vi to skove ved at slette rodknudepunktet A og de tre kanter, der forbandt rodknudepunktet til knudepunkterne B, C og D.

# 3) Binært træ

En treddatastruktur, hvor hver knudepunkt højst har to underknudepunkter, kaldes et binært træ. Et binært træ er den mest populære træstatastruktur og bruges i en række applikationer som ekspressionsevaluering, databaser osv.

Den følgende figur viser et binært træ.

Binært træ

I ovenstående figur ser vi, at knudepunkterne A, B og D har to børn hver. Et binært træ, hvor hver node har nøjagtigt nul eller to børn, kaldes et fuldt binært træ. I dette træ er der ingen noder, der har et barn.

Et komplet binært træ har et binært træ, der er fuldstændigt fyldt med undtagelse af det laveste niveau, der er fyldt fra venstre mod højre. Det binære træ vist ovenfor er et fuldt binært træ.

Følgende er et simpelt program til at demonstrere et binært træ. Bemærk, at output af træet er inordnet traversal sekvens af input træet.

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

Produktion:

Binært træ oprettet:

5 10 15 20 30 40 45

hvordan man fjerner element fra array i java med eksempel

# 4) Binært søgetræ

Det binære træ, der bestilles, kaldes det binære søgetræ. I et binært søgetræ er knudepunkterne til venstre mindre end rodknudepunktet, mens knudepunkterne til højre er større end eller lig med rodknudepunktet.

Et eksempel på et binært søgetræ er vist nedenfor.

Binært søgetræ

I ovenstående figur kan vi se, at de venstre knudepunkter alle er mindre end 20, hvilket er rodelementet. De højre noder er derimod større end rodnoden. Det binære søgetræ bruges i søge- og sorteringsteknikker.

# 5) Ekspressionstræ

Et binært træ, der bruges til at evaluere enkle aritmetiske udtryk kaldes et ekspressionstræ.

Et simpelt udtryktræ vises nedenfor.

Ekspressionstræ

I ovenstående prøveekspressionstræ repræsenterer vi udtrykket (a + b) / (a-b). Som vist i ovenstående figur repræsenterer ikke-bladknudepunkterne i træet operatorerne af udtrykket, mens bladknudepunkterne repræsenterer operanderne.

Ekspressionstræer bruges hovedsageligt til at løse algebraiske udtryk.

Træ gennemgange teknikker

Vi har set lineære datastrukturer som arrays, sammenkædede lister, stakke, køer osv. Alle disse datastrukturer har en fælles traverseringsteknik, der kun krydser strukturen på en måde, dvs. lineært.

Men i tilfælde af træer har vi forskellige gennemgange teknikker som angivet nedenfor:

# 1) I rækkefølge: I denne traversale teknik krydser vi først det venstre undertræ, indtil der ikke er flere noder i det venstre undertræ. Efter dette besøger vi rodnoden og fortsætter derefter med at krydse det rigtige undertræ, indtil der ikke er flere noder at krydse i det rigtige undertræ. Således er rækkefølgen af ​​inOrder traversal venstre-> root-> højre.

# 2) Forudbestilling: For forudbestilling af traversal teknik behandler vi rodnoden først, derefter krydser vi hele venstre undertræ og til sidst krydser vi det højre undertræ. Derfor er rækkefølgen af ​​forudgående traversal rod-> venstre-> højre.

# 3) Efterbestilling: I post-order traversal teknik krydser vi det venstre undertræ, derefter det højre undertræ og endelig rodnoden. Rækkefølgen af ​​gennemkørsel for postorderteknikken er venstre-> højre-> rod.

Hvis n er rodknudepunktet, og 'l' og 'r' er henholdsvis venstre og højre knudepunkt i træet, er træets traversalgoritmer som følger:

I rækkefølge (lnr) algoritme:

  1. Gå gennem venstre undertræ ved hjælp af inOrder (venstre - Undertræ).
  2. Besøg rodnoden (n).
  3. Gå gennem højre undertræ ved hjælp af inOrder (højre - undertræ).

Forudbestil (nlr) algoritme:

  1. Besøg rodnoden (n).
  2. Kryds venstre undertræ ved hjælp af forudbestilling (venstre undertræ).
  3. Kryds det højre undertræ ved hjælp af forudbestilling (højre undertræ).

Postorder (lrn) algoritme:

  1. Kryds venstre undertræ ved hjælp af postOrder (venstre undertræ).
  2. Kryds det rigtige undertræ ved hjælp af postOrder (højre undertræ).
  3. Besøg rodnoden (n).

Fra ovenstående algoritmer for traversal teknikker ser vi, at teknikkerne kan anvendes til et givet træ på en rekursiv måde for at få det ønskede resultat.

Overvej følgende træ.

Postorder (lrn) algoritme

hvordan ser et internetmodem ud

Ved hjælp af de ovennævnte tværgående teknikker er traversalsekvensen for det ovenstående træ angivet nedenfor:

  1. InOrder gennemgang: 2 3 5 6 10
  2. Forudbestilling gennemgang: 6 3 2 5 10
  3. PostOrder traversal: 2 5 3 10 6

Konklusion

Træer er en ikke-lineær hierarkisk datastruktur, der bruges i mange applikationer inden for softwarefeltet.

I modsætning til lineære datastrukturer, der kun har en måde at krydse listen på, kan vi krydse træer på en række forskellige måder. Vi havde en detaljeret undersøgelse af traversal teknikker og de forskellige typer træer i denne vejledning.

=> Se på C ++ begynderguiden her

Anbefalet læsning

^