А
заперечення дискретної математики
Бінарне дерево
Є різні типи бінарного дерева але тут ми обговоримо різницю Повне бінарне дерево і Повне бінарне дерево .
Повне бінарне дерево:
Повне двійкове дерево — це двійкове дерево, в якому усі вузли мають 0 або 2 нащадків . Іншими словами, повне бінарне дерево — це бінарне дерево, у якому всі вузли, окрім листових, мають двох нащадків.
Повне бінарне дерево
Дозволяти, i бути числом внутрішніх вузлів
п буде загальна кількість вузлів
л бути кількістю листків
л бути кількістю рівнівПотім,
Кількість листочків становить (i + 1) .
Загальна кількість вузлів становить (2i + 1) .
Кількість внутрішніх вузлів становить (n – 1) / 2 .
Кількість листочків становить (n + 1) / 2 .
Загальна кількість вузлів становить (2л – 1) .
Кількість внутрішніх вузлів становить (l – 1) .
Кількість листків не більше (2л- 1) .
Повне бінарне дерево:
Бінарне дерево називається a повне бінарне дерево якщо всі його рівні, крім, можливо, останнього рівня, мають максимальну кількість можливих вузлів, і всі вузли в останній рівень з'являється якомога ліворуч .
java заміна всього
Повне бінарне дерево
Є 2 моменти, які ви можете розпізнати тут,
- Крайня ліва сторона листкового вузла завжди має бути заповнена першою.
- Не обов’язково, щоб останній листовий вузол мав правого брата.
Перегляньте наступні приклади, щоб краще зрозуміти повне та повне бінарне дерево.
Приклад 1:
Ні повний, ні повний
- Вузол C тому має лише одну дитину, це не повне бінарне дерево.
- Вузол C також має праву дитину, але не має лівої дитини, отже це також не повне бінарне дерево.
Отже, бінарне дерево, показане вище, є ні повне, ні повне бінарне дерево.
приклад 2:
Повний, але не повний
- Усі вузли мають те й інше 0 або 2 потомство, отже, це повне бінарне дерево .
Це не повне бінарне дерево, оскільки вузол Б не має дітей, тоді як node C має дітей, і відповідно до повного бінарного дерева, вузли повинні бути заповнені з ліва сторона .Отже, бінарне дерево, показане вище, є a Повне бінарне дерево і це так не повне бінарне дерево.
приклад 3:
Повний, але не повний
Це повне бінарне дерево, оскільки всі вузли залишаються заповненими.
- Вузол B має лише одного дочірнього елемента, отже, це не повне бінарне дерево.
Отже, бінарне дерево, показане вище, є a Повне бінарне дерево і це так не повне бінарне дерево.
Приклад 4:
підключитися до бази даних javaПовний і повний
- Це Повний двійковий файл дерево, оскільки всі вузли є залишилося заповненим .
- Усі вузли мають те й інше 0 або 2 потомство, отже, це a повне бінарне дерево .
Отже, двійкове дерево, показане вище як повне, так і повне бінарне дерево.
| Так ні. | Повне бінарне дерево | Повне бінарне дерево |
| 1. | У повному бінарному дереві вузол на останньому рівні може мати лише одного дочірнього елемента. | У повному бінарному дереві вузол не може мати лише одного дочірнього елемента. |
| 2. | У повному бінарному дереві вузол має бути заповнений зліва направо. | У повному бінарному дереві немає порядку заповнення вузлів. |
| 3. | Повні бінарні дерева в основному використовуються в структурах даних на основі купи. | Повне бінарне дерево не має застосування як таке, але його також називають правильним двійковим деревом. |
| 4. | Повне двійкове дерево також називають майже повним бінарним деревом. | Повне бінарне дерево також називається правильним бінарним деревом або 2-деревом. |
| 5 | Повне бінарне дерево повинно мати весь листковий вузол на однаковій глибині. | У повному бінарному дереві листовий рівень не обов’язково повинен бути на одній глибині. |