trees c basic terminology
Aquest tutorial en profunditat sobre els arbres C ++ explica els tipus d'arbres, les tècniques de creuament d'arbres i la terminologia bàsica amb imatges i exemples de programes:
En aquesta sèrie C ++, fins ara hem vist l’estructura lineal de dades tant de naturalesa estàtica com dinàmica. Ara procedirem amb l’estructura de dades no lineal. La primera estructura de dades d'aquesta categoria és 'Arbres'.
Els arbres són estructures de dades jeràrquiques no lineals. Un arbre és una col·lecció de nodes connectats entre si mitjançant 'arestes' dirigides o no dirigides. Un dels nodes es designa com a 'Node arrel' i la resta de nodes s'anomenen nodes fills o nodes fulla del node arrel.
En general, cada node pot tenir tants fills, però només un node pare.
=> Mireu tota la sèrie de formació C ++
Els nodes d'un arbre estan al mateix nivell anomenats nodes germans o poden tenir una relació pare-fill. Els nodes amb el mateix pare són nodes germans.
Què aprendreu:
Arbres en C ++
A continuació es mostra un arbre d'exemple amb les seves diverses parts.
Repassem les definicions d’alguns termes bàsics que fem servir per als arbres.
- Node arrel: Aquest és el node més alt de la jerarquia d'arbres. Al diagrama anterior, el node A és el node arrel. Tingueu en compte que el node arrel no té cap pare.
- Node de fulla: És el node inferior amb una jerarquia d'arbres. Els nodes de fulla són els nodes que no tenen cap node fill. També es coneixen com a nodes externs. Els nodes E, F, G, H i C de l’arbre anterior són tots nodes de fulles.
- Subarbre: El subarbre representa diversos descendents d'un node quan l'arrel no és nul·la. Un arbre sol estar format per un node arrel i un o més subarbres. Al diagrama anterior, (B-E, B-F) i (D-G, D-H) són subarbres.
- Node pare: Qualsevol node excepte el node arrel que tingui un node fill i una vora cap amunt cap al pare.
- Node de l'ancestre: És qualsevol node predecessor en un camí des de l'arrel fins a aquest node. Tingueu en compte que l'arrel no té cap avantpassat. Al diagrama anterior, A i B són els avantpassats d’E.
- Clau: Representa el valor d'un node.
- Nivell: Representa la generació d’un node. Un node arrel sempre es troba al nivell 1. Els nodes fills de l'arrel són al nivell 2, els néts de l'arrel al nivell 3, etc. En general, cada node es troba en un nivell superior al seu pare.
- Camí: El camí és una seqüència d’arestes consecutives. Al diagrama anterior, el camí cap a E és A => B-> E.
- Titulació: El grau d’un node indica el nombre de fills que té un node. Al diagrama anterior, el grau de B i D és 2 cadascun mentre que el grau de C és 0.
Tipus d’arbres C ++
L'estructura de dades de l'arbre es pot classificar en els següents subtipus, tal com es mostra al diagrama següent.
# 1) Arbre general
L’arbre general és la representació bàsica d’un arbre. Té un node i un o més nodes fills. El node de nivell superior és a dir, el node arrel està present al nivell 1 i tots els altres nodes poden estar presents a diversos nivells.
A la figura següent es mostra un arbre general.
Com es mostra a la figura anterior, un arbre general pot contenir qualsevol nombre de subarbres. Els nodes B, C i D estan presents al nivell 2 i són nodes germans. De la mateixa manera, els nodes E, F, G i H també són nodes germans.
Els nodes presents a diferents nivells poden presentar una relació pare-fill. A la figura anterior, els nodes B, C i D són fills d’A. Els nodes E i F són fills de B, mentre que els nodes G i H són fills de D.
L'arbre general es mostra a continuació mitjançant la implementació de 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; } Sortida:
L’arbre general creat és el següent:
10
/
20 30
/
40
# 2) Boscos
Sempre que suprimim el node arrel de l’arbre i les vores que uneixen els elements de nivell següent i l’arrel, obtenim conjunts d’arbres diferents com es mostra a continuació.
A la figura anterior, vam obtenir dos boscos eliminant el node arrel A i les tres vores que connectaven el node arrel als nodes B, C i D.
# 3) Arbre binari
Una estructura de dades d’arbre en què cada node té com a màxim dos nodes fills s’anomena arbre binari. Un arbre binari és l’estructura de dades d’arbre més popular i s’utilitza en diverses aplicacions com ara avaluació d’expressions, bases de dades, etc.
La figura següent mostra un arbre binari.
A la figura anterior, veiem que els nodes A, B i D tenen dos fills cadascun. Un arbre binari en què cada node té exactament zero o dos fills es denomina arbre binari complet. En aquest arbre, no hi ha nodes que tinguin un fill.
Un arbre binari complet té un arbre binari que s’omple completament a excepció del nivell més baix que s’omple d’esquerra a dreta. L’arbre binari que es mostra més amunt és un arbre binari complet.
A continuació es mostra un programa senzill per demostrar un arbre binari. Tingueu en compte que la sortida de l'arbre és la seqüència de recorregut inorder de l'arbre d'entrada.
#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: '< Sortida:
Arbre binari creat:
5 10 15 20 30 40 45
# 4) Arbre de cerca binària
L’arbre binari que s’ordena s’anomena arbre de cerca binari. En un arbre de cerca binari, els nodes a l'esquerra són inferiors al node arrel, mentre que els nodes a la dreta són majors o iguals al node arrel.
A continuació es mostra un exemple d’arbre de cerca binari.
A la figura anterior, podem veure que els nodes de l’esquerra són inferiors a 20, que és l’element arrel. Els nodes de la dreta, en canvi, són més grans que el node arrel. L’arbre de cerca binari s’utilitza en tècniques de cerca i classificació.
# 5) Arbre d'expressió
Un arbre binari que s’utilitza per avaluar expressions aritmètiques senzilles s’anomena arbre d’expressions.
A continuació es mostra un arbre d’expressions senzill.
A l'arbre d'expressions de mostra anterior, representem l'expressió (a + b) / (a-b). Com es mostra a la figura anterior, els nodes que no són de fulla de l'arbre representen els operadors de l'expressió mentre que els nodes de fulla representen els operands.
hi ha vr per a Xbox One
Els arbres d’expressió s’utilitzen principalment per resoldre expressions algebraiques.
Tècniques transversals d’arbres
Hem vist estructures de dades lineals com ara matrius, llistes enllaçades, piles, cues, etc. Totes aquestes estructures de dades tenen una tècnica de recorregut comuna que travessa l’estructura només d’una manera, és a dir, linealment.
Però, en el cas dels arbres, tenim diferents tècniques de recorregut que es detallen a continuació:
# 1) En ordre: En aquesta tècnica de recorregut, recorrem primer el subarbre esquerre fins que no hi hagi més nodes al subarbre esquerre. Després d'això, visitem el node arrel i després procedim a recórrer el subarbre dret fins que no hi hagi més nodes a travessar al subarbre dret. Per tant, l'ordre del recorregut dins de l'Ordre és a l'esquerra-> arrel-> dreta.
# 2) Reserva prèvia: Per a la tècnica de travessia prèvia ordre, primer processem el node arrel, després recorrem tot el subarbre esquerre i, finalment, travessem el subarbre dret. Per tant, l’ordre del recorregut de l’ordre previ és root-> left-> right.
# 3) Post-comanda: En la tècnica de recorregut postordre, recorrem el subarbre esquerre, després el subarbre dret i, finalment, el node arrel. L'ordre de recorregut per a la tècnica del postordre és left-> right-> root.
Si n és el node arrel i 'l' i 'r' són nodes esquerra i dret de l'arbre respectivament, els algoritmes de recorregut de l'arbre són els següents:
Per ordre (lnr):
- Recorre el subarbre esquerre amb inOrder (esquerra- Subarbre).
- Visiteu el node arrel (n).
- Recorre el subarbre dret utilitzant inOrder (subarbre dret).
Algorisme de reserva (nlr):
- Visiteu el node arrel (n).
- Recórrer el subarbre esquerre utilitzant el preordre (esquerra-subarbre).
- Recórrer el subarbre dret utilitzant el preordre (dret-subarbre).
Algorisme de postordre (lrn):
- Recórrer el subarbre esquerre mitjançant postOrder (esquerre-subarbre).
- Recórrer el subarbre dret mitjançant postOrder (dret-subarbre).
- Visiteu el node arrel (n).
A partir dels algoritmes anteriors de tècniques de recorregut, veiem que les tècniques es poden aplicar a un arbre determinat de manera recursiva per obtenir el resultat desitjat.
Penseu en l'arbre següent.
Mitjançant les tècniques de recorregut anteriors, a continuació es dóna la seqüència de recorregut de l’arbre anterior:
- Recorregut a l’ordre: 2 3 5 6 10
- Recorregut de preordre: 6 3 2 5 10
- Recorregut postordre: 2 5 3 10 6
Conclusió
Els arbres són una estructura de dades jeràrquica no lineal que s’utilitza en moltes aplicacions del camp del programari.
A diferència de les estructures de dades lineals que només tenen una manera de recórrer la llista, podem travessar els arbres de diverses maneres. En aquest tutorial vam tenir un estudi detallat de les tècniques de recorregut i dels diferents tipus d’arbres.
=> Mireu aquí la guia per a principiants de C ++
Lectura recomanada
- Estructura de dades d’arbre B i arbre B + en C ++
- Estructura de dades de l'arbre binari en C ++
- Tipus de riscos en projectes de programari
- Arbre AVL i estructura de dades de Heap a C ++
- Tipus de dades Python
- 20 preguntes senzilles per comprovar el vostre programari Provant coneixements bàsics (Concurs en línia)
- Tipus de dades C ++
- Operacions bàsiques d'entrada / sortida en C ++
