Menu

Stromy v C ++: Základní terminologie, techniky procházení a typy stromů v C ++

  • Hlavní
  • Jiný
  • Stromy v C ++: Základní terminologie, techniky procházení a typy stromů v C ++

trees c basic terminology

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento podrobný výukový program o stromech C ++ vysvětluje typy stromů, techniky procházení stromů a základní terminologii s obrázky a ukázkovými programy:

V této řadě C ++ jsme zatím viděli lineární datovou strukturu statické i dynamické povahy. Nyní budeme pokračovat v nelineární datové struktuře. První datovou strukturou v této kategorii jsou „Stromy“.

Stromy jsou nelineární hierarchické datové struktury. Strom je sbírka uzlů vzájemně propojených pomocí „hran“, které jsou směrovány nebo neorientovány. Jeden z uzlů je označen jako „Kořenový uzel“ a zbývající uzly se nazývají podřízené uzly nebo listové uzly kořenového uzlu.

Obecně může mít každý uzel tolik dětí, ale pouze jeden nadřazený uzel.

=> Podívejte se na celou sérii školení C ++

Strom v C ++

Uzly stromu jsou buď na stejné úrovni zvané sesterské uzly, nebo mohou mít vztah rodič-dítě. Uzly se stejným rodičem jsou sourozenecké uzly.

Co se naučíte:

aplikace pro převod z youtube na mp3 zdarma ke stažení

Stromy v C ++

Níže je uveden ukázkový strom s různými částmi.

Strom v C ++ s různými částmi

Pojďme si projít definice některých základních pojmů, které používáme pro stromy.

  • Kořenový uzel: Toto je nejvyšší uzel ve stromové hierarchii. Ve výše uvedeném diagramu je uzel A kořenovým uzlem. Kořenový uzel nemá žádného rodiče.
  • Uzel listu: Je to nejspodnější uzel ve stromové hierarchii. Listové uzly jsou uzly, které nemají žádné podřízené uzly. Jsou také známé jako externí uzly. Uzly E, F, G, H a C ve výše uvedeném stromu jsou všechny listové uzly.
  • Podstrom: Podstrom představuje různé potomky uzlu, když kořen není null. Strom se obvykle skládá z kořenového uzlu a jednoho nebo více podstromů. Ve výše uvedeném diagramu jsou (B-E, B-F) a (D-G, D-H) podstromy.
  • Nadřazený uzel: Libovolný uzel kromě kořenového uzlu, který má podřízený uzel a hranu nahoru směrem k nadřazenému uzlu.
  • Uzel předka: Je to jakýkoli předchůdce uzel na cestě z kořene k tomuto uzlu. Kořen nemá žádné předky. Ve výše uvedeném diagramu jsou A a B předky E.
  • Klíč: Představuje hodnotu uzlu.
  • Úroveň: Představuje generování uzlu. Kořenový uzel je vždy na úrovni 1. Podřízené uzly kořene jsou na úrovni 2, vnoučata kořene jsou na úrovni 3 atd. Obecně platí, že každý uzel je na úrovni vyšší než jeho nadřazený.
  • Cesta: Cesta je posloupností po sobě jdoucích hran. Ve výše uvedeném diagramu je cesta k E A => B-> E.
  • Stupeň: Stupeň uzlu označuje počet dětí, které má uzel. Ve výše uvedeném diagramu je stupeň B a D vždy 2, zatímco stupeň C je 0.

Typy stromů C ++

Stromovou datovou strukturu lze rozdělit do následujících podtypů, jak ukazuje následující diagram.

Druhy Tree v C ++

# 1) Obecný strom

Obecný strom je základní reprezentací stromu. Má uzel a jeden nebo více podřízených uzlů. Uzel nejvyšší úrovně, tj. Kořenový uzel je přítomen na úrovni 1 a všechny ostatní uzly mohou být přítomny na různých úrovních.

Obecný strom je zobrazen na následujícím obrázku.

Obecný strom

Jak je znázorněno na výše uvedeném obrázku, obecný strom může obsahovat libovolný počet podstromů. Uzly B, C a D jsou přítomny na úrovni 2 a jsou sourozeneckými uzly. Podobně jsou uzly E, F, G a H také sourozenecké uzly.

Uzly přítomné na různých úrovních mohou vykazovat vztah rodič-dítě. Na výše uvedeném obrázku jsou uzly B, C a D dětmi A. Uzly E a F jsou dětmi B, zatímco uzly G a H jsou dětmi D.

Obecný strom je ukázán níže pomocí implementace 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ýstup:

Vytvořený obecný strom je následující:

10

/

20 30

/

40

# 2) Lesy

Kdykoli odstraníme kořenový uzel ze stromu a hrany spojující prvky další úrovně a kořen, získáme nesouvislé sady stromů, jak je znázorněno níže.

Lesy

Na výše uvedeném obrázku jsme získali dva lesy odstraněním kořenového uzlu A a tří hran, které spojovaly kořenový uzel s uzly B, C a D.

# 3) Binární strom

Stromová datová struktura, ve které má každý uzel nejvýše dva podřízené uzly, se nazývá binární strom. Binární strom je nejoblíbenější datová struktura stromu a používá se v řadě aplikací, jako je vyhodnocení výrazů, databáze atd.

Následující obrázek ukazuje binární strom.

Binární strom

Na výše uvedeném obrázku vidíme, že uzly A, B a D mají po dvou podřízených. Binární strom, ve kterém má každý uzel přesně nulu nebo dvě děti, se nazývá plný binární strom. V tomto stromu nejsou žádné uzly, které mají jedno dítě.

Kompletní binární strom má binární strom, který je zcela vyplněn, s výjimkou nejnižší úrovně vyplněné zleva doprava. Binární strom zobrazený výše je plný binární strom.

Následuje jednoduchý program pro demonstraci binárního stromu. Všimněte si, že výstupem ze stromu je inorderová traversální sekvence 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ýstup:

Binární strom vytvořen:

5 10 15 20 30 40 45

# 4) Binární vyhledávací strom

Objednaný binární strom se nazývá binární vyhledávací strom. V binárním vyhledávacím stromu jsou uzly nalevo menší než kořenový uzel, zatímco uzly napravo jsou větší nebo rovny kořenovému uzlu.

jak používat server pro založení týmu

Níže je uveden příklad binárního vyhledávacího stromu.

Binární vyhledávací strom

Na výše uvedeném obrázku vidíme, že všechny levé uzly jsou menší než 20, což je kořenový prvek. Pravé uzly jsou na druhou stranu větší než kořenový uzel. Binární vyhledávací strom se používá v technikách vyhledávání a řazení.

# 5) Strom výrazů

Binární strom, který se používá k vyhodnocení jednoduchých aritmetických výrazů, se nazývá strom výrazů.

Níže je uveden jednoduchý strom výrazů.

Výraz strom

Ve výše uvedeném ukázkovém stromu výrazů reprezentujeme výraz (a + b) / (a-b). Jak je znázorněno na výše uvedeném obrázku, nelistové uzly stromu představují operátory výrazu, zatímco listové uzly představují operandy.

Stromy výrazů se používají hlavně k řešení algebraických výrazů.

Techniky procházení stromů

Viděli jsme lineární datové struktury, jako jsou pole, propojené seznamy, komíny, fronty atd. Všechny tyto datové struktury mají společnou techniku ​​procházení, která prochází strukturou pouze jedním způsobem, tj. Lineárně.

Ale v případě stromů máme různé techniky procházení, které jsou uvedeny níže:

# 1) V pořadí: V této technice procházení nejprve projdeme levým podstromem, dokud v levém podstromu nebudou žádné další uzly. Poté navštívíme kořenový uzel a poté pokračujeme v procházení pravým podstromem, dokud v pravém podstromu nebudou žádné další uzly k procházení. Pořadí procházení inOrder je tedy vlevo -> root -> vpravo.

# 2) Předobjednávka: U techniky předobjednávky procházení nejprve zpracujeme kořenový uzel, poté projdeme celým levým podstromem a nakonec přejdeme pravým podstromem. Pořadí předobjednávky je tedy root-> left-> right.

# 3) Post-order: V technice post-order traversal procházíme levým podstromem, poté pravým podstromem a nakonec kořenovým uzlem. Pořadí procházení pro postorderovou techniku ​​je left-> right-> root.

Pokud n je kořenový uzel a „l“ a „r“ jsou levý a pravý uzel stromu, pak jsou algoritmy pro procházení stromem následující:

V pořadí (lnr) algoritmus:

  1. Procházejte levým podstromem pomocí inOrder (levý podstrom).
  2. Navštivte kořenový uzel (n).
  3. Procházejte pravý podstrom pomocí inOrder (pravý podstrom).

Algoritmus předobjednávky (NLR):

  1. Navštivte kořenový uzel (n).
  2. Procházejte levým podstromem pomocí předobjednávky (levý podstrom).
  3. Procházejte pravý podstrom pomocí předobjednávky (pravý podstrom).

Algoritmus postorder (lrn):

  1. Procházejte levým podstromem pomocí postOrder (levý podstrom).
  2. Procházejte pravý podstrom pomocí postOrder (pravý podstrom).
  3. Navštivte kořenový uzel (n).

Z výše uvedených algoritmů technik procházení vidíme, že tyto techniky lze aplikovat na daný strom rekurzivním způsobem k získání požadovaného výsledku.

Zvažte následující strom.

Algoritmus postorder (lrn)

Pomocí výše uvedených technik procházení je sekvence procházení výše uvedeného stromu uvedena níže:

  1. Traversal InOrder: 2 3 5 6 10
  2. Přechod předobjednávky: 6 3 2 5 10
  3. Přechod po objednávce: 2 5 3 10 6

Závěr

Stromy jsou nelineární hierarchická datová struktura, která se používá v mnoha aplikacích v oblasti softwaru.

Na rozdíl od lineárních datových struktur, které mají pouze jeden způsob procházení seznamu, můžeme procházet stromy různými způsoby. V tomto výukovém programu jsme měli podrobnou studii technik procházení a různých druhů stromů.

=> Prohlédněte si Průvodce pro začátečníky v C ++ zde

Doporučené čtení

^