Menu

Štruktúra dát binárneho stromu v C ++

  • Hlavná
  • Iné
  • Štruktúra dát binárneho stromu v C ++

binary tree data structure c

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento Hĺbkový výukový program o binárnom strome v C ++ vysvetľuje typy, zastúpenie, prechod, aplikácie a implementáciu binárnych stromov v C ++:

Binárny strom je široko používaná stromová dátová štruktúra. Keď má každý uzol stromu najviac dva podriadené uzly, potom sa strom nazýva Binárny strom.

Typický binárny strom bude mať teda nasledujúce komponenty:

  • Ľavý podstrom
  • Koreňový uzol
  • Pravý podstrom

=> Dajte si pozor na kompletný zoznam výukových programov C ++ v tejto sérii.

Binárny strom v C ++

Čo sa dozviete:

Binárny strom v C ++

Obrázkové znázornenie binárneho stromu je uvedené nižšie:

Obrázkové znázornenie binárneho stromu

V danom binárnom strome je maximálny počet uzlov na ľubovoľnej úrovni 2l-1kde „l“ je číslo úrovne.

V prípade koreňového uzla na úrovni 1 je teda maximálny počet uzlov = 21-1= 20= 1

Pretože každý uzol v binárnom strome má najviac dva uzly, bude maximálny počet uzlov na ďalšej úrovni 2 * 2l-1.

použitie c ++ v reálnom svete

Vzhľadom na binárny strom hĺbky alebo výšky h je maximálny počet uzlov v binárnom strome výšky h = 2h- 1.

Preto v binárnom strome s výškou 3 (zobrazený vyššie) je maximálny počet uzlov = 23-1 = 7.

Teraz poďme diskutovať o rôznych druhoch binárnych stromov.

Typy binárneho stromu

Nasledujú najbežnejšie typy binárnych stromov.

# 1) Celý binárny strom

Binárny strom, v ktorom má každý uzol 0 alebo 2 deti, sa nazýva plný binárny strom.

Celý binárny strom

Vyššie je zobrazený plný binárny strom, v ktorom vidíme, že všetky jeho uzly okrem listových majú dve deti. Ak L je počet listových uzlov a ‘l’ je počet vnútorných alebo nelistových uzlov, potom pre úplný binárny strom L = l + 1.

# 2) Kompletný binárny strom

Kompletný binárny strom má naplnené všetky úrovne okrem poslednej úrovne a posledná úroveň má všetky svoje uzly až naľavo.

Kompletný binárny strom

Strom zobrazený vyššie je úplný binárny strom. Typickým príkladom úplného binárneho stromu je binárna halda, o ktorej si povieme ďalšie príručky.

# 3) Perfektný binárny strom

Binárny strom sa nazýva dokonalý, keď všetky jeho vnútorné uzly majú dve deti a všetky listové uzly sú na rovnakej úrovni.

Dokonalý binárny strom

Vyššie uvedený príklad binárneho stromu je dokonalý binárny strom, pretože každý z jeho uzlov má dve deti a všetky listové uzly sú na rovnakej úrovni.

Dokonalý binárny strom s výškou h má 2h- 1 počet uzlov.

# 4) Degenerovaný strom

Binárny strom, kde má každý vnútorný uzol iba jedno dieťa, sa nazýva zdegenerovaný strom.

Zdegenerovaný strom

Strom zobrazený vyššie je zdegenerovaný strom. Pokiaľ ide o výkon tohto stromu, zdegenerované stromy sú rovnaké ako zoznamy prepojených odkazov.

# 5) Vyvážený binárny strom

Binárny strom, v ktorom sa hĺbka dvoch podstromov každého uzla nikdy nelíši o viac ako 1, sa nazýva vyvážený binárny strom.

Vyvážený binárny strom

Binárny strom zobrazený vyššie je vyváženým binárnym stromom, pretože hĺbka dvoch podstromov každého uzla nie je väčšia ako 1. Stromy AVL, o ktorých sa budeme baviť v nasledujúcich cvičeniach, sú bežným vyváženým stromom.

Reprezentácia binárneho stromu

Binárny strom je alokovaný do pamäte dvoma spôsobmi.

# 1) Postupné zastúpenie

Toto je najjednoduchšia technika na ukladanie stromovej dátovej štruktúry. Na uloženie uzlov stromu sa používa pole. Počet uzlov v strome určuje veľkosť poľa. Koreňový uzol stromu je uložený pri prvom indexe v poli.

Všeobecne platí, že ak je uzol uložený na ithpotom je ľavé a pravé dieťa uložené na 2i a 2i + 1.

Zvážte nasledujúci binárny strom.

Ukážka binárneho stromu

Postupné znázornenie vyššie uvedeného binárneho stromu je nasledovné:

postupné znázornenie binárneho stromu

Vo vyššie uvedenom znázornení vidíme, že ľavé a pravé dieťa každého uzla je uložené na miestach 2 * (node_location) a 2 * (node_location) +1.

Napríklad, umiestnenie uzla 3 v poli je 3. Takže jeho ľavé dieťa bude umiestnené na 2 * 3 = 6. Jeho pravé dieťa bude na mieste 2 * 3 +1 = 7. Ako vidíme v poli, deti z 3, ktoré sú 6 a 7, sú umiestnené na miestach 6 a 7 v poli.

Postupné znázornenie stromu je neefektívne, pretože pole, ktoré sa používa na ukladanie uzlov stromu, zaberá veľa miesta v pamäti. Ako strom rastie, toto zastúpenie sa stáva neefektívnym a ťažko zvládnuteľným.

Táto nevýhoda je prekonaná uložením uzlov stromu do prepojeného zoznamu. Upozorňujeme, že ak je strom prázdny, potom sa prvé umiestnenie s koreňovým uzlom nastaví na 0.

# 2) Reprezentácia prepojeného zoznamu

V tomto type znázornenia sa na uloženie uzlov stromu používa prepojený zoznam. Niekoľko uzlov je rozptýlených v pamäti na nesúvislých miestach a uzly sú spojené pomocou vzťahu rodič - dieťa ako strom.

ako vytvoriť firewall od nuly

Nasledujúci diagram zobrazuje prepojené zastúpenie zoznamu pre strom.

Prepojený zoznam

Ako je znázornené na obrázku vyššie, každý uzol prepojeného zoznamu má tri komponenty:

  • Ľavý ukazovateľ
  • Dátová časť
  • Pravý ukazovateľ

Ľavý ukazovateľ má ukazovateľ na ľavé dieťa uzla; pravý ukazovateľ má ukazovateľ na pravé dieťa uzla, zatiaľ čo dátová časť obsahuje skutočné údaje uzla. Ak pre daný uzol (listový uzol) neexistujú žiadne potomky, potom je ľavý a pravý ukazovateľ pre tento uzol nastavený na hodnotu null, ako je to znázornené na obrázku vyššie.

Implementácia binárneho stromu v C ++

Ďalej vyvíjame program binárnych stromov pomocou prepojenej reprezentácie zoznamu v C ++. Pomocou štruktúry deklarujeme jeden uzol a potom pomocou triedy vypracujeme prepojený zoznam uzlov.

#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

Binárny strom Traversal

O prechodoch sme už hovorili v našom základnom návode na stromy. V tejto časti implementujeme program, ktorý vkladá uzly do binárneho stromu a tiež demonštruje všetky tri priechody, tj. Inorder, preorder a postorder pre binárny strom.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(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 bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Výkon:

Prechod v poradí:

A B C D E F G

Prechod zásielkového obchodu:

G F E D C B A

Predobjednať prechod:

A B C D E F G

Aplikácie binárneho stromu

Binárny strom sa používa v mnohých aplikáciách na ukladanie údajov.

Niektoré z dôležitých aplikácií binárnych stromov sú uvedené nižšie:

  • Binárne vyhľadávacie stromy: Binárne stromy sa používajú na vytvorenie binárneho vyhľadávacieho stromu, ktorý sa používa v mnohých vyhľadávacích aplikáciách, ako sú množiny a mapy, v mnohých jazykových knižniciach.
  • Hašovacie stromy: Používa sa na overenie hašovania hlavne v špecializovaných aplikáciách na podpis obrázkov.
  • Hromady: Hromady sa používajú na implementáciu prioritných front, ktoré sa používajú pre smerovače, plánovanie procesorov v operačnom systéme atď.
  • Huffmanovo kódovanie: Huffmanov kódovací strom sa používa v kompresných algoritmoch (napríklad pri kompresii obrázkov) aj v kryptografických aplikáciách.
  • Syntaxový strom: Kompilátory často konštruujú syntaxové stromy, ktoré nie sú ničím iným ako binárnymi stromami na analýzu výrazov použitých v programe.

Záver

Binárne stromy sú široko používané dátové štruktúry v softvérovom priemysle. Binárne stromy sú stromy, ktorých uzly majú najviac dva podriadené uzly. Videli sme rôzne druhy binárnych stromov ako úplný binárny strom, úplný binárny strom, dokonalý binárny strom, zdegenerovaný binárny strom, vyvážený binárny strom atď.

Údaje v binárnom strome je možné prechádzať aj pomocou techník prechádzania inorder, preorder a postorder, ktoré sme videli v našom predchádzajúcom tutoriáli. V pamäti môže byť binárny strom reprezentovaný pomocou prepojeného zoznamu (nesúvislá pamäť) alebo polí (sekvenčné znázornenie).

Reprezentácia prepojeného zoznamu je v porovnaní s poliami efektívnejšia, pretože polia zaberajú veľa miesta.

=> Vyskúšajte tu najlepšie výukové programy pre C ++.

Odporúčané čítanie

^