Меню

Структура на данните на двоичното дърво в C ++

binary tree data structure c

Опитайте Нашия Инструмент За Премахване На Проблемите

Този задълбочен урок за двоично дърво в C ++ обяснява типове, представяне, обход, приложения и внедряване на двоични дървета в C ++:

Двоичното дърво е широко използвана дървовидна структура от данни. Когато всеки възел на дърво има най-много два дъщерни възела, тогава дървото се нарича двоично дърво.

Така че едно типично двоично дърво ще има следните компоненти:

  • Ляво поддърво
  • Корен възел
  • Право поддърво

=> Внимавайте за пълния списък с уроци за C ++ в тази поредица.

Двоично дърво в C ++

Какво ще научите:

Двоично дърво в C ++

Изобразително представяне на двоично дърво е показано по-долу:

Изобразително представяне на двоично дърво

В дадено двоично дърво максималният брой възли на всяко ниво е 2l-1където „l“ е номерът на нивото.

По този начин в случай на коренния възел на ниво 1, максималният брой възли = 21-1= 20= 1

Тъй като всеки възел в двоично дърво има най-много два възела, максималните възли на следващото ниво ще бъдат 2 * 2l-1.

как да намеря ключ за мрежова сигурност на рутера

Като се има предвид двоично дърво с дълбочина или височина h, максималният брой възли в двоично дърво с височина h = 2з- 1.

Следователно в двоично дърво с височина 3 (показано по-горе) максималният брой възли = 23-1 = 7.

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

Видове двоично дърво

Следват най-често срещаните видове бинарни дървета.

# 1) Пълно двоично дърво

Двоично дърво, в което всеки възел има 0 или 2 деца, се нарича пълно двоично дърво.

Пълно двоично дърво

По-горе е показано пълно двоично дърво, в което можем да видим, че всички негови възли с изключение на листните възли имат две деца. Ако L е броят на листовите възли и ‘l’ е броят на вътрешните или нелистовите възли, тогава за пълно двоично дърво, L = l + 1.

# 2) Пълно двоично дърво

Пълното двоично дърво има всички нива запълнени, с изключение на последното ниво, а последното ниво има всичките си възли колкото вляво.

Пълно двоично дърво

Показаното по-горе дърво е пълно двоично дърво. Типичен пример за пълно бинарно дърво е двоична купчина, която ще обсъдим в следващите уроци.

# 3) Перфектно двоично дърво

Бинарното дърво се нарича перфектно, когато всичките му вътрешни възли имат две деца и всички листни възли са на едно и също ниво.

Перфектно двоично дърво

Примерът за двоично дърво, показан по-горе, е перфектно двоично дърво, тъй като всеки от неговите възли има две деца и всички листни възли са на едно и също ниво.

Перфектното двоично дърво с височина h има 2з- 1 брой възли.

# 4) Дегенерирано дърво

Двоично дърво, където всеки вътрешен възел има само едно дете, се нарича дегенерирано дърво.

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

Показаното по-горе дърво е дегенеративно дърво. Що се отнася до производителността на това дърво, изродените дървета са същите като свързаните списъци.

# 5) Балансирано двоично дърво

Двоично дърво, в което дълбочината на двете поддървета на всеки възел никога не се различава с повече от 1, се нарича балансирано двоично дърво.

Балансирано двоично дърво

Показаното по-горе двоично дърво е балансирано двоично дърво, тъй като дълбочината на двете поддървета на всеки възел е не повече от 1. AVL дърветата, които ще обсъдим в следващите ни уроци, са общо балансирано дърво.

Представяне на двоично дърво

На двоично дърво се разпределя памет по два начина.

# 1) Последователно представяне

Това е най-простата техника за съхраняване на дървесна структура от данни. За съхранение на дървесните възли се използва масив. Броят на възлите в дървото определя размера на масива. Коренният възел на дървото се съхранява при първия индекс в масива.

По принцип, ако възел се съхранява в iтиместоположението, тогава лявото и дясното дете се съхраняват съответно на 2i и 2i + 1 място.

Помислете за следното двоично дърво.

Примерно двоично дърво

Последователното представяне на горното двоично дърво е както следва:

последователно представяне на двоично дърво

В горното представяне виждаме, че лявото и дясното дете на всеки възел се съхраняват на места 2 * (node_location) и 2 * (node_location) +1 съответно.

Например, местоположението на възел 3 в масива е 3. Така че лявото му дете ще бъде поставено на 2 * 3 = 6. Десното му дете ще бъде на местоположението 2 * 3 +1 = 7. Както виждаме в масива, деца от 3, които са 6 и 7, се поставят на място 6 и 7 в масива.

Последователното представяне на дървото е неефективно, тъй като масивът, който се използва за съхраняване на дървесните възли, заема много място в паметта. С нарастването на дървото това представяне става неефективно и трудно за управление.

Този недостатък се преодолява чрез съхраняване на дървесните възли в свързан списък. Имайте предвид, че ако дървото е празно, тогава първото местоположение, съхраняващо кореновия възел, ще бъде зададено на 0.

# 2) Представяне на свързан списък

В този тип представяне се използва свързан списък за съхраняване на дървесните възли. Няколко възла са разпръснати в паметта на несвързани места и възлите са свързани, като се използва връзката родител-дете като дърво.

Следващата диаграма показва свързано представяне на списък за дърво.

Представяне на свързан списък

Както е показано в горното представяне, всеки свързан възел със списък има три компонента:

  • Ляв показалец
  • Част от данни
  • Десен показалец

Лявият указател има указател към лявото дете на възела; десният указател има указател към дясното дете на възела, докато частта с данни съдържа действителните данни на възела. Ако няма деца за даден възел (листен възел), тогава лявият и десният указател за този възел са настроени на нула, както е показано на горната фигура.

Внедряване на двоично дърво в C ++

След това разработваме програма за двоично дърво, използвайки представяне на свързан списък в C ++. Използваме структура, за да декларираме един възел и след това, използвайки клас, разработваме свързан списък с възли.

#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

Преминаване на двоично дърво

Вече обсъдихме обходи в нашия основен урок за дървета. В този раздел нека приложим програма, която вмъква възли в двоичното дърво и също така демонстрира всичките три обхождания, т.е. inorder, preorder и postorder, за двоично дърво.

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

Изход:

Вътрешно обръщане:

A B C D E F G

Обръщане на поръчки по пощата:

G F E D C B A

Обръщане на предварителна поръчка:

A B C D E F G

Приложения на двоично дърво

В много приложения за съхраняване на данни се използва двоично дърво.

Някои от важните приложения на двоичните дървета са изброени по-долу:

  • Двоични дървета за търсене: Бинарните дървета се използват за изграждане на двоично дърво за търсене, което се използва в много приложения за търсене като набори и карти в много езикови библиотеки.
  • Хеш дървета: Използва се за проверка на хешове главно в специализирани приложения за подписване на изображения.
  • Купчини: Купчините се използват за внедряване на приоритетни опашки, които се използват за рутери, процесори за планиране в операционната система и т.н.
  • Кодиране на Huffman: Дървото за кодиране на Huffman се използва в алгоритми за компресиране (като компресиране на изображения), както и в криптографски приложения.
  • Синтаксисно дърво: Компилаторите често конструират синтаксисни дървета, които не са нищо друго освен двоични дървета, за да анализират изразите, използвани в програмата.

Заключение

Бинарните дървета са широко използвани структури от данни в софтуерната индустрия. Бинарните дървета са дърветата, чиито възли имат най-много два дъщерни възела. Виждали сме различни видове двоични дървета като пълно двоично дърво, пълно двоично дърво, перфектно двоично дърво, дегенерирано двоично дърво, балансирано двоично дърво и т.н.

Данните от двоичното дърво също могат да бъдат премествани, използвайки техники за обръщане inorder, preorder и postorder, които сме виждали в предишния ни урок. В паметта бинарно дърво може да бъде представено чрез свързан списък (несвързана памет) или масиви (последователно представяне).

Представянето на свързан списък е по-ефективно в сравнение с масивите, тъй като масивите заемат много място.

=> Вижте най-добрите уроци за обучение на C ++ тук.

как да отворите jnlp файл

Препоръчително четене

^