Бінарне дерево означає, що вузол може мати максимум двох дочірніх елементів. Тут сама бінарна назва говорить про те, що 'два'; отже, кожен вузол може мати 0, 1 або 2 дітей.

Давайте розберемо бінарне дерево на прикладі.

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

У наведеному вище дереві вузол 1 містить два покажчики, тобто лівий і правий покажчики, що вказують на лівий і правий вузол відповідно. Вузол 2 містить обидва вузли (лівий і правий вузол); отже, він має два покажчики (лівий і правий). Вузли 3, 5 і 6 є листовими вузлами, тому всі ці вузли містять НУЛЬ вказівник на лівій і правій частинах.

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

• На кожному рівні i максимальна кількість вузлів становить 2ⁱ.
• Висота дерева визначається як найдовший шлях від кореневого вузла до листкового вузла. Дерево, яке показано вище, має висоту, що дорівнює 3. Отже, максимальна кількість вузлів на висоті 3 дорівнює (1+2+4+8) = 15. Загалом, максимальна кількість вузлів, можлива на висоті h є (2⁰+ 2¹+ 2²+….2^ч) = 2^h+1-1.
• Мінімальна кількість вузлів, можлива на висоті h, дорівнює h+1 .
• Якщо кількість вузлів мінімальна, то висота дерева буде максимальною. І навпаки, якщо кількість вузлів максимальна, то висота дерева буде мінімальною.

Якщо у двійковому дереві є 'n' кількість вузлів.

Мінімальна висота може бути обчислена як:

Як ми знаємо,

n = 2^h+1-1

є особливим символом

n+1 = 2^h+1

Взявши колоду з обох сторін,

журнал₂(n+1) = log2(2^h+1)

git rebase

журнал₂(n+1) = h+1

h = журнал₂(n+1) - 1

Максимальну висоту можна обчислити як:

Як ми знаємо,

n = h+1

h= n-1

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

Існує чотири типи бінарного дерева:

Повне/ правильне/ суворе бінарне дерево Повне бінарне дерево Ідеальне бінарне дерево Вироджене бінарне дерево Збалансоване бінарне дерево

1. Повне/ правильне/ суворе бінарне дерево

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

Давайте розглянемо простий приклад повного бінарного дерева.

У наведеному вище дереві ми можемо спостерігати, що кожен вузол містить або нуль, або два дочірніх вузла; отже, це повне бінарне дерево.

масив байтів до рядка java

Властивості повного бінарного дерева

• Кількість листових вузлів дорівнює кількості внутрішніх вузлів плюс 1. У наведеному вище прикладі кількість внутрішніх вузлів дорівнює 5; отже, кількість листових вузлів дорівнює 6.
• Максимальна кількість вузлів дорівнює кількості вузлів у бінарному дереві, тобто 2^h+1-1.
• Мінімальна кількість вузлів у повному бінарному дереві становить 2*h-1.
• Мінімальна висота повного бінарного дерева становить журнал₂(n+1) - 1.
• Максимальну висоту повного бінарного дерева можна обчислити як:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

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

Повне бінарне дерево — це дерево, у якому всі вузли повністю заповнені, крім останнього рівня. На останньому рівні всі вузли повинні бути максимально лівими. У повному бінарному дереві вузли слід додавати зліва.

встановити роздільник java

Давайте створимо повне бінарне дерево.

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

Властивості повного бінарного дерева

• Максимальна кількість вузлів у повному бінарному дереві становить 2^h+1- 1.
• Мінімальна кількість вузлів у повному бінарному дереві становить 2^ч.
• Мінімальна висота повного бінарного дерева становить журнал₂(n+1) - 1.
• Максимальна висота повного бінарного дерева становить

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

Дерево є ідеальним бінарним деревом, якщо всі внутрішні вузли мають 2 дочірніх вузла, а всі листові вузли знаходяться на одному рівні.

Давайте розглянемо простий приклад ідеального бінарного дерева.

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

Примітка: усі ідеальні двійкові дерева є повними двійковими деревами, а також повними двійковими деревами, але навпаки невірно, тобто всі повні двійкові дерева та повні двійкові дерева є ідеальними двійковими деревами.

Вироджене бінарне дерево

Вироджене бінарне дерево — це дерево, у якому всі внутрішні вузли мають лише одного дочірнього елемента.

Давайте розберемося з виродженим бінарним деревом на прикладах.

Мультиплексор 2 до 1

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

Наведене вище дерево також є виродженим бінарним деревом, оскільки всі вузли мають лише одного дочірнього елемента. Це також відоме як лівостороннє дерево, оскільки всі вузли мають лише лівого дочірнього елемента.

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

Збалансоване бінарне дерево — це дерево, у якому ліве та праве дерева відрізняються щонайбільше на 1. Наприклад, AVL і Червоно-чорні дерева є збалансованим бінарним деревом.

Розберемо збалансоване бінарне дерево на прикладах.

Наведене вище дерево є збалансованим двійковим деревом, оскільки різниця між лівим піддеревом і правим піддеревом дорівнює нулю.

Наведене вище дерево не є збалансованим двійковим деревом, оскільки різниця між лівим і правим піддеревом більше 1.

Реалізація бінарного дерева

Двійкове дерево реалізується за допомогою покажчиків. Перший вузол у дереві представлено кореневим покажчиком. Кожен вузол у дереві складається з трьох частин, тобто даних, лівого вказівника та правого вказівника. Щоб створити бінарне дерево, нам спочатку потрібно створити вузол. Ми створимо вузол, визначений користувачем, як показано нижче:

 struct node { int data, struct node *left, *right; } 

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

Програма двійкового дерева на C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Наведений вище код рекурсивно викликає функцію create() і створює новий вузол під час кожного рекурсивного виклику. Коли всі вузли створені, утворюється бінарна деревовидна структура. Процес відвідування вузлів відомий як обхід дерева. Існує три типи обходів, які використовуються для відвідування вузла:

• Обхід у порядку
• Обхід попереднього замовлення
• Обхід поштового замовлення