trees c basic terminology
Denne grundige opplæringen om C ++ trær forklarer tretyper, treovergangsteknikker og grunnleggende terminologi med bilder og eksempelprogrammer:
I denne C ++ - serien har vi så langt sett den lineære datastrukturen av både statisk og dynamisk natur. Nå skal vi fortsette med den ikke-lineære datastrukturen. Den første datastrukturen i denne kategorien er 'Trees'.
Trær er ikke-lineære hierarkiske datastrukturer. Et tre er en samling noder som er koblet til hverandre ved hjelp av 'kanter' som enten er rettet eller ikke-rettet. En av nodene er betegnet som 'rotnode' og de resterende nodene kalles undernoder eller bladnodene til rotnoden.
Generelt kan hver node ha like mange barn, men bare en foreldrenode.
=> Sjekk ut hele C ++ treningsserien
Noder på et tre er enten på samme nivå som kalles søsternoder, eller de kan ha et foreldre-barn-forhold. Noder med samme foreldre er søskenoder.
Hva du vil lære:
Trær i C ++
Nedenfor er et eksempel på et tre med forskjellige deler.
La oss gå gjennom definisjonene av noen grunnleggende begreper som vi bruker for trær.
- Rotknutepunkt: Dette er den øverste noden i trehierarkiet. I diagrammet ovenfor er node A rotnoden. Merk at rotnoden ikke har noen foreldre.
- Bladknute: Det er den nederste mest noden i et trehierarki. Bladnoder er nodene som ikke har noen noder for barn. De er også kjent som eksterne noder. Noder E, F, G, H og C i treet ovenfor er alle bladnoder.
- Undertrær: Subtrær representerer forskjellige etterkommere av en node når roten ikke er null. Et tre består vanligvis av en rotnode og ett eller flere undertrær. I diagrammet ovenfor er (B-E, B-F) og (D-G, D-H) undertrær.
- Overordnet node: Enhver node unntatt rotnoden som har en undernode og en kant oppover mot foreldren.
- Ancestor Node: Det er en hvilken som helst forgjengerknute på en bane fra roten til den noden. Merk at roten ikke har noen forfedre. I diagrammet ovenfor er A og B forfedrene til E.
- Nøkkel: Den representerer verdien av en node.
- Nivå: Representerer genereringen av en node. En rotnode er alltid på nivå 1. Barnnoder til roten er på nivå 2, barnebarn av roten er på nivå 3 og så videre. Generelt er hver node på et nivå høyere enn foreldrene.
- Sti: Banen er en sekvens av påfølgende kanter. I diagrammet ovenfor er banen til E A => B-> E.
- Grad: Grad av en node angir antall barn som en node har. I diagrammet ovenfor er graden av B og D 2 hver mens graden av C er 0.
Typer C ++ trær
Tredatastrukturen kan klassifiseres i følgende undertyper som vist i diagrammet nedenfor.
# 1) Generelt tre
Det generelle treet er den grunnleggende representasjonen av et tre. Den har en node og en eller flere underordnede noder. Toppnodenoden, dvs. rotnoden, er tilstede på nivå 1, og alle de andre nodene kan være til stede på forskjellige nivåer.
Et generelt tre er vist i figuren nedenfor.
Som vist i figuren ovenfor, kan et generelt tre inneholde et hvilket som helst antall undertrær. Nodene B, C og D er tilstede på nivå 2 og er søskenoder. Tilsvarende er noder E, F, G og H også søskenoder.
Nodene som er tilstede på forskjellige nivåer kan utvise et foreldre-barn-forhold. I figuren ovenfor er noder B, C og D barn av A. Noder E og F er barn av B mens noder G og H er barn av D.
Det generelle treet er demonstrert nedenfor ved bruk av C ++ implementering:
hva er nettverkssikkerhetsnøkkelen for trådløs
#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; } Produksjon:
Generelt tre opprettet er som følger:
10
/
20 30
/
40
# 2) Skog
Hver gang vi sletter rotnoden fra treet og kantene som går sammen med neste nivåelementer og roten, får vi usammenhengende sett med trær som vist nedenfor.
hva er forskjellen mellom ytre sammenføyning og venstre sammenføyning
I figuren ovenfor fikk vi to skoger ved å slette rotknutepunktet A og de tre kantene som koblet rotknutepunktet til nodene B, C og D.
# 3) Binært tre
En tredatastruktur der hver node maksimalt har to underordnede noder kalles et binært tre. Et binært tre er den mest populære tredatastrukturen og brukes i en rekke applikasjoner som uttrykksevaluering, databaser, etc.
Følgende figur viser et binært tre.
I figuren ovenfor ser vi at nodene A, B og D har to barn hver. Et binært tre der hver node har nøyaktig null eller to barn kalles et fullstendig binært tre. I dette treet er det ingen noder som har ett barn.
Et komplett binært tre har et binært tre som er fullstendig fylt med unntak av det laveste nivået som er fylt fra venstre til høyre. Det binære treet vist ovenfor er et fullstendig binært tre.
Følgende er et enkelt program for å demonstrere et binært tre. Vær oppmerksom på at utdataene fra treet er inordnet traversalsekvens for inndatatreet.
#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: '< Produksjon:
Binært tre opprettet:
5 10 15 20 30 40 45
# 4) Binært søketre
Det binære treet som er bestilt kalles det binære søketreet. I et binært søketre er nodene til venstre mindre enn rotnoden mens nodene til høyre er større enn eller lik rotnoden.
Et eksempel på et binært søketre er vist nedenfor.
I figuren ovenfor kan vi se at de venstre nodene alle er mindre enn 20, som er rotelementet. De høyre nodene er derimot større enn rotnoden. Det binære søketreet brukes i søke- og sorteringsteknikker.
# 5) Uttrykkstreet
Et binært tre som brukes til å evaluere enkle aritmetiske uttrykk kalles et uttrykkstre.
Et enkelt uttrykkstre er vist nedenfor.
I det ovennevnte prøveuttrykkstreet representerer vi uttrykket (a + b) / (a-b). Som vist i figuren ovenfor representerer ikke-bladnodene i treet operatørene av uttrykket mens bladnodene representerer operandene.
Uttrykkstrær brukes hovedsakelig til å løse algebraiske uttrykk.
Tree Traversal Techniques
Vi har sett lineære datastrukturer som matriser, koblede lister, stabler, køer osv. Alle disse datastrukturene har en felles krysseteknikk som bare krysser strukturen på en måte, dvs. lineært.
Men når det gjelder trær, har vi forskjellige traversale teknikker som er oppført nedenfor:
# 1) I rekkefølge: I denne traverserteknikken krysser vi først venstre undertre til det ikke er flere noder i venstre undertreet. Etter dette besøker vi rotnoden og fortsetter deretter å krysse høyre undertre til det ikke er flere noder å krysse i riktig undertre. Dermed er rekkefølgen på inOrder traversal venstre-> rot-> høyre.
forskjellen mellom c ++ og java
# 2) Forhåndsbestill: For preorder traversal teknikk, behandler vi rotnoden først, deretter krysser vi hele venstre undertre og til slutt krysser vi høyre subtree. Derfor er rekkefølgen på forhåndsbestilling gjennomgang rot-> venstre-> høyre.
# 3) Etterbestilling: I post-order traversal teknikken krysser vi venstre undertre, deretter høyre undertre og til slutt rotnoden. Rekkefølgen for traversering for postorderteknikken er venstre-> høyre-> rot.
Hvis n er rotknutepunktet og 'l' og 'r' er henholdsvis venstre og høyre knutepunkt på treet, er treovergangsalgoritmene som følger:
I rekkefølge (lnr) algoritme:
- Travers left subtree using inOrder (left- Subtree).
- Besøk rotnoden (n).
- Kryss høyre undertrær ved hjelp av inOrder (høyre - subtree).
Forhåndsbestillingsalgoritme (nlr):
- Besøk rotnoden (n).
- Kryss venstre undertre ved å bruke forhåndsbestilling (venstre undertre).
- Kryss høyre undertrær ved hjelp av forhåndsbestilling (høyre undertrær).
Postorder (lrn) algoritme:
- Travers left subtree using postOrder (left-subtree).
- Kryss høyre undertrær ved hjelp av postOrder (høyre undertrær).
- Besøk rotnoden (n).
Fra de ovennevnte algoritmene for traversale teknikker, ser vi at teknikkene kan brukes på et gitt tre på en rekursiv måte for å oppnå ønsket resultat.
Tenk på følgende tre.
Ved å bruke de ovennevnte traverseringsteknikkene er traversalsekvensen for treet ovenfor gitt nedenfor:
- InOrder-traversering: 2 3 5 6 10
- Forhåndsbestilling: 6 3 2 5 10
- Gjennomgang av bestilling: 2 5 3 10 6
Konklusjon
Trær er en ikke-lineær hierarkisk datastruktur som brukes i mange applikasjoner i programvarefeltet.
I motsetning til lineære datastrukturer som bare har en måte å krysse listen på, kan vi krysse trær på en rekke måter. Vi hadde en detaljert studie av traversale teknikker og de forskjellige treslagene i denne opplæringen.
=> Ta en titt på C ++ Beginners Guide her
Anbefalt lesing
- B Tree og B + Tree Datastruktur i C ++
- Datastruktur for binært tre i C ++
- Typer av risikoer i programvareprosjekter
- AVL Tree and Heap Datastruktur i C ++
- Python datatyper
- 20 enkle spørsmål for å sjekke programvaren din Testing grunnleggende kunnskap (Online Quiz)
- C ++ datatyper
- Grunnleggende inngangs- / utgangsoperasjoner i C ++
