trees c basic terminology
Denna fördjupade handledning om C ++ träd förklarar trädtyper, trädgenomgångstekniker och grundläggande terminologi med bilder och exempelprogram:
c ++ exempel på reguljärt uttryck
I denna C ++ - serie har vi hittills sett den linjära datastrukturen av både statisk och dynamisk natur. Nu fortsätter vi med den icke-linjära datastrukturen. Den första datastrukturen i denna kategori är 'Träd'.
Träd är icke-linjära hierarkiska datastrukturer. Ett träd är en samling noder som är kopplade till varandra med hjälp av ”kanter” som antingen är riktade eller oriktade. En av noderna betecknas som ”rotnod” och de återstående noderna kallas undernoder eller bladnoderna till rotnoden.
I allmänhet kan varje nod ha lika många barn men bara en föräldernod.
=> Kolla in hela C ++ träningsserien
Noder i ett träd är antingen på samma nivå som kallas systernoder eller så kan de ha ett förhållande mellan förälder och barn. Noder med samma förälder är syskonnoder.
Vad du kommer att lära dig:
Träd i C ++
Nedan ges ett exempel på ett träd med dess olika delar.
Låt oss gå igenom definitionerna av några grundläggande termer som vi använder för träd.
- Rotnod: Detta är den översta noden i trädhierarkin. I ovanstående diagram är nod A rotnoden. Observera att rotnoden inte har någon förälder.
- Bladnod: Det är den nedersta noden i en trädhierarki. Bladnoder är de noder som inte har några undernoder. De är också kända som externa noder. Noder E, F, G, H och C i ovanstående träd är alla bladnoder.
- Subträd: Subträd representerar olika ättlingar till en nod när roten inte är null. Ett träd består vanligtvis av en rotnod och ett eller flera underträd. I ovanstående diagram är (B-E, B-F) och (D-G, D-H) underträd.
- Föräldernod: Vilken nod som helst utom rotnoden som har en undernod och en kant uppåt mot föräldern.
- Ancestor Node: Det är vilken föregångare som helst på en väg från roten till den noden. Observera att roten inte har några förfäder. I ovanstående diagram är A och B förfäder till E.
- Nyckel: Det representerar värdet på en nod.
- Nivå: Representerar genereringen av en nod. En rotnod är alltid på nivå 1. Barnnoder i roten är på nivå 2, barnbarn till roten är på nivå 3 och så vidare. I allmänhet är varje nod högre än sin förälder.
- Väg: Banan är en sekvens av på varandra följande kanter. I ovanstående diagram är vägen till E A => B-> E.
- Grad: Graden av en nod anger antalet barn som en nod har. I ovanstående diagram är graden B och D 2 vardera medan graden C är 0.
Typer av C ++ träd
Träddatastrukturen kan klassificeras i följande undertyper som visas i nedanstående diagram.
# 1) Allmänt träd
Det allmänna trädet är den grundläggande representationen av ett träd. Den har en nod och en eller flera underordnade noder. Toppnivånoden, dvs. rotnoden, finns på nivå 1 och alla andra noder kan finnas på olika nivåer.
Ett allmänt träd visas i figuren nedan.
Som visas i figuren ovan kan ett allmänt träd innehålla valfritt antal underträd. Noderna B, C och D finns på nivå 2 och är syskonnoder. På samma sätt är noder E, F, G och H också syskonnoder.
Noder som finns på olika nivåer kan uppvisa ett förhållande mellan förälder och barn. I figuren ovan är noder B, C och D barn till A. Noder E och F är barn till B medan noder G och H är barn till D.
Det allmänna trädet visas nedan med 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:
Allmänt träd skapat är som följer:
10
/
20 30
/
40
# 2) Skogar
Närhelst vi tar bort rotnoden från trädet och kanterna som förenar nästa nivåelement och roten, får vi ojämna uppsättningar av träd som visas nedan.
I figuren ovan erhöll vi två skogar genom att radera rotnoden A och de tre kanterna som anslöt rotnoden till noderna B, C och D.
# 3) Binärt träd
En träddatastruktur där varje nod har högst två barnnoder kallas ett binärt träd. Ett binärt träd är den mest populära trädatastrukturen och används i en rad applikationer som uttrycksutvärdering, databaser etc.
Följande bild visar ett binärt träd.
I figuren ovan ser vi att noderna A, B och D har två barn vardera. Ett binärt träd där varje nod har exakt noll eller två barn kallas ett fullständigt binärt träd. I det här trädet finns det inga noder som har ett barn.
Ett komplett binärt träd har ett binärt träd som är helt fyllt med undantag för den lägsta nivån som fylls från vänster till höger. Det binära trädet som visas ovan är ett fullständigt binärt träd.
java skapa en rad objekt
Följande är ett enkelt program för att demonstrera ett binärt träd. Observera att utmatningen från trädet är inordnad traversal sekvens för inmatningsträdet.
#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äd skapat:
5 10 15 20 30 40 45
# 4) Binärt sökträd
Det binära trädet som beställs kallas det binära sökträdet. I ett binärt sökträd är noder till vänster mindre än rotnoden medan noder till höger är större än eller lika med rotnoden.
Ett exempel på ett binärt sökträd visas nedan.
I figuren ovan kan vi se att de vänstra noderna alla är mindre än 20 vilket är rotelementet. De högra noderna är å andra sidan större än rotnoden. Det binära sökträdet används i sök- och sorteringstekniker.
# 5) Uttrycksträd
Ett binärt träd som används för att utvärdera enkla aritmetiska uttryck kallas ett uttrycksträd.
Ett enkelt uttrycksträd visas nedan.
I ovanstående exempeluttrycksträd representerar vi uttrycket (a + b) / (a-b). Som visas i figuren ovan representerar trädets icke-bladnoder operatörerna av uttrycket medan bladnoderna representerar operanderna.
Uttrycksträd används främst för att lösa algebraiska uttryck.
Trädgenomgångstekniker
Vi har sett linjära datastrukturer som matriser, länkade listor, staplar, köer, etc. Alla dessa datastrukturer har en gemensam genomkörningsteknik som endast passerar strukturen på ett sätt, dvs. linjärt.
Men när det gäller träd har vi olika genomkörningstekniker som anges nedan:
# 1) I ordning: I denna genomkörningsteknik korsar vi först det vänstra underträdet tills det inte finns fler noder i det vänstra underträdet. Efter detta besöker vi rotnoden och fortsätter sedan att korsa rätt subtree tills det inte finns fler noder att passera i rätt subtree. Således är ordningen på inOrder-traversal vänster-> root-> höger.
# 2) Förbeställning: För förbeställning av traversalsteknik bearbetar vi rotnoden först, sedan passerar vi hela vänster subtree och slutligen passerar vi rätt subtree. Därför är ordningen på förbeställning genomgående rot-> vänster-> höger.
# 3) Efterbeställning: I post-order traversal-teknik passerar vi vänster subtree, sedan höger subtree och slutligen rotnoden. Ordningsföljden för postordertekniken är vänster-> höger-> rot.
Om n är rotnoden och 'l' och 'r' är vänster respektive höger noder i trädet, så är trädgenomgångsalgoritmerna följande:
I ordning (lnr) algoritm:
- Korsa vänster underträd med inBeställning (vänster- Subträd).
- Besök rotnoden (n).
- Korsa höger subtree med inOrder (höger subtree).
Förbeställ algoritm (nlr):
- Besök rotnoden (n).
- Korsa vänster underträd med förbeställning (vänster subtree).
- Korsa rätt underträd med förbeställning (höger underträd).
Postorder (lrn) algoritm:
hur man öppnar en .jar fil
- Korsa vänster subtree med postOrder (vänster-subtree).
- Korsa rätt subtree med postOrder (höger subtree).
- Besök rotnoden (n).
Från ovanstående algoritmer för traversaltekniker ser vi att teknikerna kan tillämpas på ett visst träd på ett rekursivt sätt för att få önskat resultat.
Tänk på följande träd.
Med hjälp av ovannämnda genomgångstekniker ges traverssekvensen för ovanstående träd nedan:
- InOrder-genomgång: 2 3 5 6 10
- Förbeställning: 6 3 2 5 10
- PostOrder traversal: 2 5 3 10 6
Slutsats
Träd är en icke-linjär hierarkisk datastruktur som används i många applikationer inom programvarufältet.
Till skillnad från linjära datastrukturer som bara har ett sätt att korsa listan, kan vi korsa träd på olika sätt. Vi hade en detaljerad studie av traversal tekniker och de olika typerna av träd i denna handledning.
=> Ta en titt på C ++ nybörjarguiden här
Rekommenderad läsning
- B-träd och B + träddatastruktur i C ++
- Datastruktur för binärt träd i C ++
- Typer av risker i programvaruprojekt
- AVL-träd- och högdatastruktur i C ++
- Python-datatyper
- 20 enkla frågor för att kontrollera din programvara Testa grundläggande kunskap [Online Quiz]
- C ++ datatyper
- Grundläggande in- / utmatningsfunktioner i C ++