trees c basic terminology
Táto podrobná príručka o stromoch C ++ vysvetľuje typy stromov, techniky prechodu stromov a základnú terminológiu pomocou obrázkov a príkladov programov:
V tejto sérii C ++ sme zatiaľ videli lineárnu dátovú štruktúru statickej aj dynamickej povahy. Teraz budeme pokračovať v nelineárnej dátovej štruktúre. Prvá dátová štruktúra v tejto kategórii je „Stromy“.
Stromy sú nelineárne hierarchické dátové štruktúry. Strom je súbor uzlov navzájom spojených pomocou „hrán“, ktoré sú buď nasmerované, alebo neusmernené. Jeden z uzlov je označený ako „Root node“ a zvyšné uzly sa nazývajú dcérske uzly alebo listové uzly koreňového uzla.
Všeobecne môže mať každý uzol toľko detí, ale iba jeden nadradený uzol.
=> Vyskúšajte celú školiacu sériu C ++
Uzly stromu sú buď na rovnakej úrovni ako sesterské uzly, alebo môžu mať vzťah rodič - dieťa. Uzly s rovnakým rodičom sú súrodenecké uzly.
Čo sa dozviete:
Stromy v C ++
Nižšie je uvedený príkladový strom s rôznymi časťami.
Prejdime si definície niektorých základných pojmov, ktoré používame pre stromy.
- Koreňový uzol: Toto je najvyšší uzol v stromovej hierarchii. Na vyššie uvedenom diagrame je uzol A koreňovým uzlom. Upozorňujeme, že koreňový uzol nemá žiadneho rodiča.
- Uzol listu: Je to najspodnejší uzol v stromovej hierarchii. Listové uzly sú uzly, ktoré nemajú žiadne podradené uzly. Sú tiež známe ako externé uzly. Uzly E, F, G, H a C vo vyššie uvedenom strome sú všetky listové uzly.
- Podstrom: Podstrom predstavuje rôznych potomkov uzla, keď koreň nie je prázdny. Strom sa zvyčajne skladá z koreňového uzla a jedného alebo viacerých podstromov. Na vyššie uvedenom diagrame (B-E, B-F) a (D-G, D-H) sú podstromy.
- Nadradený uzol: Ľubovoľný uzol okrem koreňového uzla, ktorý má dcérsky uzol a hranu smerom hore k rodičovi.
- Uzol predka: Je to akýkoľvek predchodca uzol na ceste od koreňa k tomuto uzlu. Upozorňujeme, že koreň nemá žiadnych predkov. Na vyššie uvedenom diagrame sú A a B predkovia E.
- Kľúč: Predstavuje hodnotu uzla.
- Úroveň: Predstavuje generovanie uzla. Koreňový uzol je vždy na úrovni 1. Podriadené uzly koreňa sú na úrovni 2, vnúčatá koreňa sú na úrovni 3 atď. Všeobecne je každý uzol na úrovni vyššej ako jeho nadradený.
- Cesta: Cesta je postupnosťou po sebe idúcich hrán. Vo vyššie uvedenom diagrame je cesta k E A => B-> E.
- Stupeň: Stupeň uzla označuje počet detí, ktoré má uzol. Na vyššie uvedenom diagrame sú stupne B a D vždy 2, zatiaľ čo stupne C sú 0.
Typy stromov C ++
Stromovú dátovú štruktúru je možné rozdeliť do nasledujúcich podtypov, ako je znázornené na nasledujúcom diagrame.
# 1) Všeobecný strom
Všeobecný strom je základné znázornenie stromu. Má uzol a jeden alebo viac podradených uzlov. Uzol najvyššej úrovne, t. J. Koreňový uzol, je prítomný na úrovni 1 a všetky ostatné uzly môžu byť prítomné na rôznych úrovniach.
ako otvoriť binárny súbor
Všeobecný strom je zobrazený na obrázku nižšie.
Ako je znázornené na obrázku vyššie, všeobecný strom môže obsahovať ľubovoľný počet podstromov. Uzly B, C a D sú prítomné na úrovni 2 a sú súrodeneckými uzlami. Podobne sú uzly E, F, G a H tiež súrodenecké uzly.
Uzly prítomné na rôznych úrovniach môžu vykazovať vzťah rodiča a dieťaťa. Na vyššie uvedenom obrázku sú uzly B, C a D deťmi A. Uzly E a F sú deťmi B, zatiaľ čo uzly G a H sú deťmi D.
Všeobecný strom je demonštrovaný nižšie pomocou implementácie 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; }
Výkon:
Vytvorený všeobecný strom je nasledovný:
10
/
20 30
/
40
# 2) Lesy
Kedykoľvek odstránime koreňový uzol zo stromu a hrany spájajúce prvky nasledujúcej úrovne a koreň, získame nesúvislé sady stromov, ako je uvedené nižšie.
Na vyššie uvedenom obrázku sme získali dva lesy odstránením koreňového uzla A a troch okrajov, ktoré spájali koreňový uzol s uzlami B, C a D.
# 3) Binárny strom
Stromová dátová štruktúra, v ktorej má každý uzol najviac dva podriadené uzly, sa nazýva binárny strom. Binárny strom je najpopulárnejšia dátová štruktúra stromu a používa sa v rade aplikácií, ako je vyhodnocovanie výrazov, databázy atď.
Nasledujúci obrázok zobrazuje binárny strom.
Na vyššie uvedenom obrázku vidíme, že uzly A, B a D majú po dve deti. Binárny strom, v ktorom má každý uzol presne nulu alebo dve deti, sa nazýva plný binárny strom. V tomto strome nie sú žiadne uzly, ktoré majú jedno dieťa.
Kompletný binárny strom má binárny strom, ktorý je úplne vyplnený, s výnimkou najnižšej úrovne, ktorá je vyplnená zľava doprava. Binárny strom zobrazený vyššie je úplný binárny strom.
Nasleduje jednoduchý program na demonštráciu binárneho stromu. Všimnite si, že výstupom stromu je inorderová traversálna sekvencia vstupného stromu.
#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: '< Výkon:
Vytvorený binárny strom:
5 10 15 20 30 40 45
# 4) Binárny vyhľadávací strom
Objednaný binárny strom sa nazýva binárny vyhľadávací strom. V binárnom vyhľadávacom strome sú uzly vľavo menšie ako koreňový uzol, zatiaľ čo uzly vpravo sú väčšie alebo rovnaké ako koreňový uzol.
Nižšie je uvedený príklad binárneho vyhľadávacieho stromu.
ako vytvoriť jednostránkovú aplikáciu pomocou angularjs
Na vyššie uvedenom obrázku vidíme, že ľavé uzly sú všetky menšie ako 20, čo je koreňový prvok. Pravé uzly sú naopak väčšie ako koreňový uzol. Binárny vyhľadávací strom sa používa v technikách vyhľadávania a triedenia.
# 5) Strom výrazov
Binárny strom, ktorý sa používa na vyhodnotenie jednoduchých aritmetických výrazov, sa nazýva strom výrazov.
Nižšie je uvedený jednoduchý strom výrazov.
Vo vyššie uvedenom vzorovom strome výrazov reprezentujeme výraz (a + b) / (a-b). Ako je znázornené na vyššie uvedenom obrázku, nelistové uzly stromu predstavujú operátory výrazu, zatiaľ čo listové uzly predstavujú operandy.
Stromy výrazov sa používajú hlavne na riešenie algebraických výrazov.
Techniky prechodu stromov
Videli sme lineárne dátové štruktúry, ako sú polia, prepojené zoznamy, zásobníky, fronty atď. Všetky tieto dátové štruktúry majú spoločnú techniku prechádzania, ktorá prechádza štruktúrou iba jedným spôsobom, t. J. Lineárne.
Ale v prípade stromov máme rôzne techniky prechodu, ktoré sú uvedené nižšie:
# 1) V poradí: Pri tejto traverzovej technike najskôr prechádzame ľavým podstromom, až kým v ľavom podstrome už nie sú žiadne ďalšie uzly. Potom navštívime koreňový uzol a potom pokračujeme v prechode pravým podstromom, až kým v pravom podstrome nebudú ďalšie uzly, ktoré je potrebné prechádzať. Poradie prechodu inOrder je teda vľavo -> root -> vpravo.
# 2) Predobjednávka: Pri technike preorder traversal najskôr spracujeme koreňový uzol, potom prechádzame celým ľavým podstromom a nakoniec prechádzame pravým podstromom. Poradie preobjednávania je teda root-> doľava-> doprava.
# 3) Objednávka: V technike post-order traversal prechádzame ľavým podstromom, potom pravým podstromom a nakoniec koreňovým uzlom. Poradie prechodu pre techniku postorder je vľavo-> vpravo-> koreň.
Ak n je koreňový uzol a „l“ a „r“ sú ľavý a pravý uzol stromu, potom sú algoritmy prechodu stromom nasledujúce:
V poradí (lnr) algoritmus:
- Prejdite ľavým podstromom pomocou inOrder (ľavý podstrom).
- Navštívte koreňový uzol (n).
- Prejdite pravý podstrom pomocou inOrder (pravý podstrom).
Algoritmus predobjednávky (NLR):
- Navštívte koreňový uzol (n).
- Prejdite ľavým podstromom pomocou predobjednávky (ľavý podstrom).
- Prejdite pravým podstromom pomocou predobjednávky (pravý podstrom).
Algoritmus postorder (lrn):
- Prejdite ľavým podstromom pomocou postOrder (ľavý podstrom).
- Prejdite pravým podstromom pomocou postOrder (pravý podstrom).
- Navštívte koreňový uzol (n).
Z vyššie uvedených algoritmov techník prechodu vidíme, že tieto techniky je možné aplikovať na daný strom rekurzívnym spôsobom, aby sa dosiahol požadovaný výsledok.
Zvážte nasledujúci strom.
Použitím vyššie uvedených techník prechodu je postupnosť prechodu pre vyššie uvedený strom uvedená nižšie:
- Traverz InOrder: 2 3 5 6 10
- Prechod objednávky: 6 3 2 5 10
- Prechod po objednávke: 2 5 3 10 6
Záver
Stromy sú nelineárna hierarchická dátová štruktúra, ktorá sa používa v mnohých aplikáciách v oblasti softvéru.
Na rozdiel od lineárnych dátových štruktúr, ktoré môžu prechádzať zoznamom iba jedným spôsobom, môžeme stromy prechádzať rôznymi spôsobmi. V tomto výučbe sme mali podrobnú štúdiu techník prechodu a rôznych druhov stromov.
ako otvoriť súbor .swf
=> Tu si pozrite príručku pre začiatočníkov v C ++
Odporúčané čítanie
- Dátová štruktúra stromu B a stromu B + v C ++
- Štruktúra dát binárneho stromu v C ++
- Typy rizík v softvérových projektoch
- Dátová štruktúra stromu a haldy AVL v C ++
- Dátové typy v Pythone
- 20 jednoduchých otázok na kontrolu vášho softvéru Testovanie základných znalostí [online kvíz]
- Dátové typy C ++
- Základné operácie vstupu / výstupu v C ++