Різниця між повним бінарним деревом і повним бінарним деревом

Повне бінарне дерево проти повне бінарне дерево

Бінарне дерево - це дерево, на якому кожен вузол має одного або двох дітей. У двійковому дереві у вузлі не може бути більше двох дітей. У двійковому дереві дітей називають «лівими» та «правими» дітьми. Дочірні вузли містять посилання на свого батька. Повне бінарне дерево - це двійкове дерево, в якому кожен рівень бінарного дерева повністю заповнений, крім останнього рівня. На невиконаному рівні вузли кріпляться, починаючи з самого лівого положення. Повне бінарне дерево - це дерево, в якому кожен вузол на дереві має двох дітей, крім листя дерева.

Що таке повне бінарне дерево?

Повне бінарне дерево - це двійкове дерево, в якому кожен вузол на дереві має рівно нуль або двох дітей. Іншими словами, кожен вузол на дереві, крім листя, має рівно двох дітей. На малюнку 1 зображено повне бінарне дерево. У повному двійковому дереві кількість вузлів (n), кількість лав (l) та кількість внутрішніх вузлів (i) пов'язані особливим чином, так що якщо ви знаєте будь-який з них, ви можете визначити інші два значення наступні:

1. Якщо повне двійкове дерево має i внутрішні вузли:

- Кількість листя l = i + 1

- Загальна кількість вузлів n = 2 * i + 1

2. Якщо повне двійкове дерево має n вузлів:

- Кількість внутрішніх вузлів i = (n-1) / 2

- Кількість листя l = (n + 1) / 2

3. Якщо повне двійкове дерево має l листя:

- Загальна кількість вузлів n = 2 * l-1

- Кількість внутрішніх вузлів i = l-1

Що таке повне бінарне дерево?

Як показано на малюнку 2, повне бінарне дерево - це двійкове дерево, в якому кожен рівень дерева повністю заповнений, крім останнього рівня. Також на останньому рівні вузли повинні бути прикріплені, починаючи з самого лівого положення. Повне двійкове дерево висотою h задовольняє наступним умовам:

- Від кореневого вузла рівень вище останнього рівня являє собою повне бінарне дерево висотою h-1

- На одному або декількох вузлах останнього рівня може бути 0 або 1 дитина

- Якщо a, b - два вузли на рівні вище останнього рівня, тоді a має більше дітей, ніж b, якщо і лише якщо a розташований ліворуч від b

Яка різниця між Повним Бінарним Деревом та Повним Бінарним Деревом?

Повні бінарні дерева та повні бінарні дерева мають чітку різницю. У той час як повне бінарне дерево - це двійкове дерево, в якому кожен вузол має нуль або двох дітей, але повне бінарне дерево - це бінарне дерево, в якому кожен рівень бінарного дерева повністю заповнений, крім останнього рівня. Деякі спеціальні структури даних, такі як купи, повинні бути повноцінними двійковими деревами, тоді як вони не повинні бути повними бінарними деревами. У повному двійковому дереві, якщо ви знаєте кількість загальних вузлів або кількість лав чи кількість внутрішніх вузлів, ви можете легко знайти інші два. Але повне бінарне дерево не має особливої ​​властивості, що стосується цих трьох атрибутів.