Меню

Структура даних двійкового дерева в C ++

binary tree data structure c

Спробуйте Наш Інструмент Для Усунення Проблем

Цей поглиблений підручник з бінарного дерева в C ++ пояснює типи, подання, обхід, програми та реалізацію бінарних дерев у C ++:

Бінарне дерево - це широко використовувана структура даних дерева. Коли кожен вузол дерева має щонайбільше два дочірні вузли, тоді дерево називається бінарним деревом.

Отже, типове двійкове дерево буде мати такі компоненти:

  • Ліве піддерево
  • Кореневий вузол
  • Праве піддерево

=> Зверніть увагу на повний перелік підручників з C ++ у цій серії.

Бінарне дерево в C ++

Що ви дізнаєтесь:

Бінарне дерево в C ++

Наочне зображення бінарного дерева показано нижче:

Живописне зображення бінарного дерева

У даному двійковому дереві максимальна кількість вузлів на будь-якому рівні дорівнює 2л-1де «l» - номер рівня.

Таким чином, у випадку кореневого вузла на рівні 1, максимальна кількість вузлів = 21-1= 20= 1

Оскільки кожен вузол у двійковому дереві має щонайбільше два вузли, максимальним числом вузлів на наступному рівні буде 2 * 2л-1.

використання c ++ в реальному світі

Враховуючи двійкове дерево глибини або висоти h, максимальна кількість вузлів у двійковому дереві висоти h = 2h- 1.

Отже, у двійковому дереві висотою 3 (показано вище) максимальна кількість вузлів = 23-1 = 7.

Тепер обговоримо різні типи бінарних дерев.

Типи бінарного дерева

Нижче наведено найпоширеніші типи бінарних дерев.

# 1) Повне двійкове дерево

Бінарне дерево, в якому кожен вузол має 0 або 2 дітей, називається повним бінарним деревом.

Повне двійкове дерево

Вище показано повне двійкове дерево, в якому ми бачимо, що всі його вузли, крім листових, мають двох дітей. Якщо L - кількість листових вузлів, а ‘l’ - кількість внутрішніх або не-листових вузлів, то для повного двійкового дерева L = l + 1.

# 2) Повне двійкове дерево

Повне двійкове дерево має всі рівні заповнені, крім останнього рівня, а останній рівень має всі свої вузли так само, як і зліва.

Повне бінарне дерево

Дерево, показане вище, є повним двійковим деревом. Типовим прикладом повного бінарного дерева є бінарна купа, про яку ми поговоримо у наступних підручниках.

# 3) Ідеальне бінарне дерево

Двійкове дерево називають ідеальним, коли всі його внутрішні вузли мають двох дітей, і всі листові вузли знаходяться на одному рівні.

Ідеальне двійкове дерево

Наведений вище приклад двійкового дерева є ідеальним двійковим деревом, оскільки кожен з його вузлів має двох дочірніх елементів, і всі листові вузли знаходяться на одному рівні.

Ідеальне двійкове дерево висотою h має 2h- 1 кількість вузлів.

# 4) Вироджене дерево

Бінарне дерево, де кожен внутрішній вузол має лише одну дочірню назву, називається виродженим деревом.

Вироджене дерево

Показане вище дерево є виродженим деревом. Що стосується продуктивності цього дерева, то вироджені дерева такі ж, як і пов'язані списки.

# 5) Збалансоване двійкове дерево

Бінарне дерево, в якому глибина двох піддерев кожного вузла ніколи не відрізняється більше ніж 1, називається збалансованим бінарним деревом.

Збалансоване двійкове дерево

Бінарне дерево, показане вище, є збалансованим бінарним деревом, оскільки глибина двох піддерев кожного вузла не більше 1. Дерева AVL, які ми збираємося обговорити в наступних навчальних посібниках, є загальним збалансованим деревом.

Представлення двійкового дерева

Двійковому дереву виділяється пам'ять двома способами.

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

Це найпростіша техніка зберігання деревної структури даних. Масив використовується для зберігання деревних вузлів. Кількість вузлів у дереві визначає розмір масиву. Кореневий вузол дерева зберігається за першим індексом у масиві.

Загалом, якщо вузол зберігається в iгорозташування, тоді це лівий та правий дочірній матеріал зберігаються у місцях 2i та 2i + 1 відповідно.

Розглянемо наступне двійкове дерево.

Зразок двійкового дерева

Послідовне представлення вищезазначеного двійкового дерева є таким:

найкраще конвертувати відео з YouTube у mp3

послідовне представлення двійкового дерева

У наведеному вище поданні ми бачимо, що лівий та правий дочірні елементи кожного вузла зберігаються у місцях 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

Застосування бінарного дерева

Бінарне дерево використовується у багатьох програмах для зберігання даних.

Нижче наведено деякі важливі програми двійкових дерев:

  • Бінарні дерева пошуку: Бінарні дерева використовуються для побудови бінарного дерева пошуку, яке використовується у багатьох пошукових програмах, таких як набори та карти у багатьох мовних бібліотеках.
  • Хеш-дерева: Використовується для перевірки хешів переважно у спеціалізованих програмах для підпису зображень.
  • Купи: Купи використовуються для реалізації пріоритетних черг, які використовуються для маршрутизаторів, процесорів планування в операційній системі тощо.
  • Кодування Хаффмана: Дерево кодування Хаффмана використовується в алгоритмах стиснення (наприклад, стиснення зображення), а також у криптографічних додатках.
  • Дерево синтаксису: Компілятори часто створюють дерева синтаксису, які є не що інше, як двійкові дерева, для аналізу виразів, що використовуються в програмі.

Висновок

Бінарні дерева - це широко використовувані структури даних у галузі програмного забезпечення. Бінарні дерева - це дерева, вузли яких мають не більше двох дочірніх вузлів. Ми бачили різні типи бінарних дерев, такі як повне бінарне дерево, повне бінарне дерево, ідеальне бінарне дерево, вироджене бінарне дерево, збалансоване бінарне дерево тощо.

Дані двійкового дерева також можна обробляти за допомогою методів обробки, замовлення та післяпорядкування, які ми бачили у нашому попередньому навчальному посібнику. У пам'яті двійкове дерево може бути представлене за допомогою пов'язаного списку (несумісна пам'ять) або масивів (послідовне представлення).

Представлення зв’язаного списку є більш ефективним у порівнянні з масивами, оскільки масиви займають багато місця.

=> Ознайомтеся з найкращими навчальними посібниками з C ++ тут.

Рекомендована література

^