Мени

Дрвеће на језику Ц ++: Основна терминологија, технике преласка и типови стабала Ц ++

  • Главни
  • Остало
  • Дрвеће на језику Ц ++: Основна терминологија, технике преласка и типови стабала Ц ++

trees c basic terminology

Испробајте Наш Инструмент За Елиминисање Проблема

шта је алат за прикупљање података

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

У овој Ц ++ серији до сада смо видели линеарну структуру података и статичке и динамичке природе. Сада ћемо наставити са нелинеарном структуром података. Прва структура података у овој категорији је „Дрвеће“.

Дрвеће су нелинеарне хијерархијске структуре података. Дрво је колекција чворова повезаних међусобно помоћу „ивица“ које су усмерене или усмерене. Један од чворова означен је као „роот чвор“, а преостали чворови називају се подређени чворови или лисни чворови коренског чвора.

Генерално, сваки чвор може имати толико деце, али само један родитељски чвор.

=> Погледајте целу серију обука за Ц ++

Дрво у Ц ++

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

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

Дрвеће у Ц ++

Доље је дат пример стабла са различитим деловима.

Дрво у Ц ++ са разним деловима

Прођимо кроз дефиниције неких основних појмова које користимо за дрвеће.

  • Коријенски чвор: Ово је највиши чвор у хијерархији стабла. На горњем дијаграму, чвор А је основни чвор. Имајте на уму да коријенски чвор нема родитеља.
  • Лист чвор: То је најнижи чвор у хијерархији стабла. Чворови листа су чворови који немају ниједан подређени чвор. Познати су и као спољни чворови. Чворови Е, Ф, Г, Х и Ц у горњем дрвету су сви чворови листова.
  • Подстабло: Подстабло представља различите потомке чвора када корен није нулл. Стабло се обично састоји од коренског чвора и једног или више подстабала. На горњем дијаграму, (Б-Е, Б-Ф) и (Д-Г, Д-Х) су подстабла.
  • Надређени чвор: Било који чвор осим основног чвора који има подређени чвор и ивицу навише према родитељу.
  • Чвор предака: То је било који претходнички чвор на путањи од корена до тог чвора. Имајте на уму да корен нема претке. На горњем дијаграму, А и Б су преци Е.
  • Кључ: Представља вредност чвора.
  • Ниво: Представља генерисање чвора. Коренски чвор је увек на нивоу 1. Дечји чворови корена су на нивоу 2, унуци корена су на нивоу 3 и тако даље. Генерално, сваки чвор је на нивоу вишем од свог родитеља.
  • Путања: Путања је низ узастопних ивица. На горњем дијаграму, пут до Е је А => Б-> Е.
  • Степен: Степен чвора указује на број деце коју чвор има. На горњем дијаграму, степен Б и Д је по 2, док је степен Ц 0.

Врсте дрвећа Ц ++

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

Врсте дрвета у језику Ц ++

# 1) Опште стабло

Опште стабло је основни приказ дрвета. Има чвор и један или више подређених чворова. Чвор највишег нивоа, тј. Коренски чвор је присутан на нивоу 1, а сви остали чворови могу бити присутни на различитим нивоима.

Опште стабло приказано је на доњој слици.

Генерал Трее

Као што је приказано на горњој слици, опште стабло може садржати неограничен број подстабала. Чворови Б, Ц и Д су присутни на нивоу 2 и чворови су браће. Слично томе, чворови Е, Ф, Г и Х такође су чворови браће и сестара.

Чворови присутни на различитим нивоима могу показивати однос родитеља и детета. На горњој слици чворови Б, Ц и Д су деца А. Чворови Е и Ф су деца Б, док су чворови Г и Х деца Д.

Опште стабло је приказано у наставку помоћу примене Ц ++:

#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; }

Излаз:

Опште створено стабло је следеће:

10

/

20 30

/

40

# 2) Шуме

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

Шуме

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

# 3) Бинарно дрво

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

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

Бинарно дрво

како уклонити ставку из низа јава

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

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

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

#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

# 4) Бинарно стабло претраживања

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

Пример бинарног стабла претраживања приказан је у наставку.

Бинарно стабло претраживања

На горњој слици можемо видети да су сви леви чворови мањи од 20, што је основни елемент. С друге стране, прави чворови су већи од коренског чвора. Бинарно стабло претраживања користи се у техникама претраживања и сортирања.

# 5) Стабло израза

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

Једноставно стабло израза приказано је испод.

Стабло израза

У горњем узорку стабла израза представљамо израз (а + б) / (а-б). Као што је приказано на горњој слици, нелистни чворови стабла представљају операторе израза, док лиснати чворови представљају операнде.

Стабла израза углавном се користе за решавање алгебарских израза.

Технике преласка дрвета

Видели смо линеарне структуре података као што су низови, повезане листе, стогови, редови итд. Све ове структуре података имају заједничку технику преласка која структуру прелази само на један начин, тј. Линеарно.

Али у случају дрвећа, имамо различите технике преласка како су доле наведене:

# 1) Редом: У овој техници преласка прво прелазимо лево подстабло док више нема чворова у левом подстаблу. Након тога, посећујемо коријенски чвор, а затим настављамо са преласком десног подстабла све док у десном подстаблу више нема чворова. Тако је редослед инОрдер преласка лево-> корен-> десно.

# 2) Преднаруџба: За технику преласка унапред, прво обрађујемо коријенски чвор, затим прелазимо цело лево подстабло и на крају прелазимо десно поддрево. Отуда је редослед преокретања предређаја корен-> лево-> десно.

# 3) Пост-поруџбина: У техници преласка пост-редоследа прелазимо лево подстабло, затим десно подстабло и на крају коријенски чвор. Редослијед преласка технике постордер је лијеви-> десни-> коријен.

Ако је н коренски чвор, а 'л' и 'р' су леви и десни чворови стабла, тада су алгоритми за прелазак стабла следећи:

Редослед (лнр) алгоритам:

најбољи начин за преузимање ИоуТубе звука
  1. Пређите левим подстаблом користећи инОрдер (лево - Подстабло).
  2. Посетите коренски чвор (н).
  3. Пређите десно поддрево помоћу инОрдер (десно поддрево).

Предбиљежба (нлр) алгоритам:

  1. Посетите коренски чвор (н).
  2. Пређите левим подстаблом помоћу предреда (лево-подстабло).
  3. Пређите преко десног подстабла користећи предредбу (десно поддрево).

Алгоритам постордер (лрн):

  1. Пређите лево подстабло помоћу постОрдер (лево-подстабло).
  2. Пређите десно поддрево помоћу постОрдер (десно-подстабло).
  3. Посетите коренски чвор (н).

Из горњих алгоритама техника преласка видимо да се технике могу применити на дато стабло на рекурзиван начин да би се добио жељени резултат.

Узмите у обзир следеће стабло.

Алгоритам постордер (лрн)

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

  1. Преокрет ИнОрдер: 2 3 5 6 10
  2. Прелазак ПреНордера: 6 3 2 5 10
  3. ПостОрдер прелазак: 2 5 3 10 6

Закључак

Дрвеће је нелинеарна хијерархијска структура података која се користи у многим апликацијама у пољу софтвера.

За разлику од линеарних структура података које имају само један начин за прелазак листе, дрвеће можемо прелазити на разне начине. У овом упутству имали смо детаљно проучавање техника преласка и различитих врста дрвећа.

=> Овде погледајте водич за почетнике за Ц ++

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

^