>
Мени

Структура података бинарног стабла у језику Ц ++

binary tree data structure c

Овај продубљени водич о бинарном стаблу на језику Ц ++ објашњава типове, представљање, прелазак, примене и примену бинарних стабала у језику Ц ++:

Бинарно стабло је широко коришћена структура података стабла. Када сваки чвор стабла има највише два подређена чвора, стабло се назива Бинарно стабло.

Тако ће типично бинарно стабло имати следеће компоненте:

  • Лево подстабло
  • Коренски чвор
  • Право подстабло

=> Пазите на комплетну листу водича за Ц ++ у овој серији.

Бинарно стабло у Ц ++

Шта ћете научити:

Бинарно стабло у Ц ++

Сликовни приказ бинарног стабла приказан је испод:

Сликовни приказ бинарног стабла

У датом бинарном стаблу, максимални број чворова на било ком нивоу је 2л-1где је „л“ број нивоа.

Дакле, у случају коренског чвора на нивоу 1, максималан број чворова = 21-1= 20= 1

Како сваки чвор у бинарном стаблу има највише два чвора, максимални чворови на следећем нивоу биће 2 * 2л-1.

С обзиром на бинарно стабло дубине или висине х, максималан број чворова у бинарном стаблу висине х = 2х- 1.

Дакле, у бинарном стаблу висине 3 (приказано горе), максималан број чворова = 23-1 = 7.

Сада ћемо разговарати о различитим врстама бинарних стабала.

Врсте бинарног стабла

Следе најчешће врсте бинарних стабала.

# 1) Потпуно бинарно стабло

Бинарно стабло у којем сваки чвор има 0 или 2 деце назива се потпуним бинарним стаблом.

Потпуно бинарно стабло

Изнад је приказано потпуно бинарно стабло у којем можемо видети да сви његови чворови, осим чворова листа, имају двоје деце. Ако је Л број чворова листа, а „л“ број унутрашњих или нелистних чворова, онда је за пуно бинарно стабло Л = л + 1.

# 2) Комплетно бинарно стабло

Комплетно бинарно стабло има све нивое испуњене, осим задњег нивоа, а последњи ниво има све своје чворове колико је лево.

Комплетно Бинарно стабло

Стабло приказано горе је комплетно бинарно стабло. Типичан пример комплетног бинарног стабла је бинарна гомила о којој ћемо разговарати у каснијим туторијалима.

како ажурирати биос на Виндовс 10

# 3) Савршено бинарно стабло

Бинарно стабло се назива савршеним када сви његови унутрашњи чворови имају двоје деце и када су сви чворови листа на истом нивоу.

Савршено бинарно стабло

Пример бинарног стабла приказан горе је савршено бинарно стабло јер сваки од његових чворова има двоје деце и сви чворови листова су на истом нивоу.

Савршено бинарно стабло висине х има 2х- 1 број чворова.

# 4) Изрођено дрво

Бинарно стабло у којем сваки унутрашњи чвор има само једно дете назива се изрођено стабло.

Изрођено дрво

Стабло приказано горе је изрођено стабло. Што се тиче перформанси овог стабла, изрођена стабла су иста као повезане листе.

# 5) Уравнотежено бинарно стабло

Бинарно стабло у којем се дубина два подстабла сваког чвора никада не разликује за више од 1 назива се уравнотежено бинарно стабло.

Уравнотежено бинарно стабло

Горе приказано бинарно стабло је уравнотежено бинарно стабло, јер дубина два подстабла сваког чвора није већа од 1. АВЛ стабла о којима ћемо разговарати у наредним туторијалима су уобичајено уравнотежено стабло.

Представљање бинарног стабла

Бинарном стаблу меморија се додељује на два начина.

# 1) Секвенцијално представљање

Ово је најједноставнија техника за чување структуре података стабла. Низ се користи за чување чворова стабла. Број чворова у стаблу дефинише величину низа. Коријенски чвор стабла чува се код првог индекса у низу.

Генерално, ако је чвор ускладиштен на итхлокација је онда лево и десно дете ускладиштено на локацији 2и и 2и + 1.

Размотрите следеће Бинарно стабло.

Узорак бинарног стабла

Секвенцијални приказ горњег бинарног стабла је следећи:

секвенцијални приказ бинарног стабла

У горњој представи видимо да су лево и десно дете сваког чвора ускладиштене на локацијама 2 * (ноде_лоцатион) и 2 * (ноде_лоцатион) +1.

На пример, локација чвора 3 у низу је 3. Дакле, његово лево дете биће постављено на 2 * 3 = 6. Његово десно дете биће на месту 2 * 3 +1 = 7. Као што видимо у низу, деца од 3, који су 6 и 7, налазе се на локацији 6 и 7 у низу.

Секвенцијални приказ стабла је неефикасан јер низ који се користи за чување чворова стабла заузима пуно простора у меморији. Како дрво расте, ова репрезентација постаје неефикасна и тешка за управљање.

Овај недостатак се превазилази складиштењем чворова стабла на повезаној листи. Имајте на уму да ако је стабло празно, тада ће прва локација која чува коријенски чвор бити постављена на 0.

# 2) Заступљеност на повезаној листи

У овом типу представљања, повезана листа се користи за чување чворова стабла. Неколико чворова је раштркано у меморији на несталним локацијама и чворови су повезани помоћу односа родитељ-дете попут дрвета.

Следећи дијаграм приказује повезан приказ листе за стабло.

Заступљеност на повезаној листи

Као што је приказано у горњој представи, сваки повезани чвор листе има три компоненте:

  • Леви показивач
  • Дио података
  • Десни показивач

Леви показивач има показивач на лево дете чвора; десни показивач има показивач на десно дете чвора, док део података садржи стварне податке чвора. Ако нема деце за дати чвор (лисни чвор), тада су леви и десни показивачи за тај чвор постављени на нулу, као што је приказано на горњој слици.

Имплементација бинарног стабла у Ц ++

Даље, развијамо програм бинарног стабла користећи повезано представљање листе у Ц ++. Користимо структуру за декларисање једног чвора, а затим помоћу класе развијамо повезану листу чворова.

#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: '<

Излаз:

Створено бинарно стабло:

5 10 15 20 30 40 45

Прелазак бинарног стабла

Већ смо разговарали о прелазима у нашем основном упутству о дрвећу. У овом одељку ћемо применити програм који убацује чворове у бинарно стабло и такође демонстрира сва три прелаза, тј. Инордер, преордер и постордер, за бинарно стабло.

мобител шпијунска апликација за андроид
#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:'<

Излаз:

Унутрашња обилазница:

А Б Ц Д Е Ф Г.

Прелазак путем поште:

Г Ф Е Д Ц Б А

Прелазак поруџбине:

А Б Ц Д Е Ф Г.

Примене бинарног стабла

Бинарно стабло се користи у многим апликацијама за чување података.

Неке од важних примена бинарних стабала су наведене у наставку:

  • Бинарна стабла за претрагу: Бинарна стабла се користе за изградњу бинарног стабла претраживања које се користи у многим апликацијама за претрагу попут скупова и мапа у многим језичким библиотекама.
  • Хасх Дрвеће: Користи се за проверу хеширања углавном у специјализованим апликацијама за потписивање слика.
  • Гомиле: Гомиле се користе за примену приоритетних редова који се користе за рутере, процесоре заказивања у оперативном систему итд.
  • Хуффман кодирање: Хуффман-ово стабло кодирања користи се у алгоритмима компресије (попут компресије слике), као и у криптографским апликацијама.
  • Синтаксно стабло: Преводитељи често конструишу стабла синтаксе која нису ништа друго до бинарна стабла за рашчлањивање израза коришћених у програму.

Закључак

Бинарна стабла су широко коришћене структуре података у индустрији софтвера. Бинарна стабла су стабла чији чворови имају највише два подређена чвора. Видели смо разне врсте бинарних стабала попут пуног бинарног стабла, комплетног бинарног стабла, савршеног бинарног стабла, изрођеног бинарног стабла, уравнотеженог бинарног стабла итд.

Подаци бинарног стабла се такође могу прелазити помоћу техника преласка унапред, унапред и унапред, које смо видели у претходном водичу. У меморији, бинарно стабло може бити представљено помоћу повезане листе (нестална меморија) или низова (секвенцијални приказ).

Приказивање повезане листе је ефикасније у поређењу са низовима, јер низови заузимају пуно простора.

=> Овде погледајте најбоље туторијале за Ц ++.

Препоручено читање

^