Бінарні дерева

Відрізняють m-арні дерева, тобто такі дерева в яких напівступінь виходу кожної вершини менше або дорівнює m (де m може дорівнювати 0,1,2,3 і т.д.). Якщо напівступінь виходу кожної вершини в точності дорівнює m, або нулеві, то таке дерево називається повним m-арным деревом. При m=2 такі дерева називаються відповідно бінарними, або повними бінарними. На рис.7. 24 (a) зображене бінарне дерево, (б)- повне бінарне дерево, а на (г) показані всі чотири можливих розташування синів деякої вершини бінарного дерева.

Рис. 7.24. Зображення бінарних дерев

У позиційному бінарному дереві кожна вершина представлена єдиним образом за допомогою рядка символів над алфавітом {0,1}, при цьому корінь характеризується порожнім рядком. Любий син вершини "u" характеризується рядком, префікс (початкова частина) якої є рядком, що характеризує "u". Прикладом бінарного дерева є фамільне дерево людини з батьком і матір'ю в якості його нащадків. Ще один приклад – це арифметичний вираз з двомісними операціями, де кожна операція являє собою розгалужений вузол з операндами в якості піддерев.

Для подання m-арного дерева в пам'яті ПЕОМ кожен елемент дерева повинний містити стільки покажчиків, скільки ребер виходить з вузла (при m=3,4.5.6 відповідно 3,4,5,6 покажчиків). Це веде до підвищеної витрати пам'яті комп’ютера, а також ускладнює алгоритми обробки дерева. Тому m-арні дерева, ліс необхідно привести до бінарного.

ПРЕДСТАВЛЕННЯ БУДЬ-ЯКОГО ДЕРЕВА, ЛІСУ БІНАРНИМИ ДЕРЕВАМИ.Дерево і ліс будь-якого виду можна перетворити єдиним образом в еквівалентне бінарне дерево.

Правило побудови бінарного дерева з будь-якого дерева:

1). У кожнім вузлі залишити тільки вітку до старшого сина (вертикальне з'єднання).

2). З'єднати горизонтальними ребрами всіх братів одного батька.

3). У такий спосіб перестроїти дерево за правилом: лівий син - це вершина, що розташована під даною; правий син - вершина, що розташована праворуч від даної (тобто на одному ярусі з нею).

4). Розгорнути дерево таким чином, щоб усі вертикальні вітки відображали лівих синів, а горизонтальні - правих.

У результаті перетворення будь-якого дерева в бінарне створюється дерево у вигляді лівого піддерева, підвішеного до кореневої вершини (див. рис. 7.25). У процесі перетворення правий покажчик кожного вузла бінарного дерева буде вказувати на сусіда за рівнем. Якщо такого немає, то правий покажчик - NIL. Лівий покажчик буде вказувати на вершину наступного рівня. Якщо такого немає, то покажчик установлюється на NIL.

Рис. 7. 25. Перетворення m-арного дерева в бінарне

а) – вихідне дерево, б) - проміжний результат перебудови, в) результат

Описаний вище метод представлення довільних упорядкованих дерев за допомогою бінарних дерев можна узагальнити на представлення довільного упорядкованого лісу.

Правило побудови бінарного дерева з лісу: корені всіх піддерев лісу з'єднати горизонтальними зв'язками. В отриманому дереві вузли в даному прикладі будуть розташовуватися на трьох рівнях. Далі перебудовувати по раніше розглянутому плані: на початку піддерево з коренем А, потім В и потім Н. У результаті перетворення упорядкованого лісу в бінарне дерево виходить повне бінарне дерево з лівим і правим піддеревом (див. рис. 7.26).

Рис. 7.26. Перетворення лісу в бінарне дерево

а) – упорядкований ліс , б) - проміжний результат перебудови,

в) представлення лісу бінарним деревом

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

Приведемо ще два важливих поняття.

Подоба бінарних дерев - два дерева подібні, якщо вони мають однакову структуру (форму). Еквівалентні бінарні дерева - два дерева еквівалентні, якщо вони подібні, і якщо відповідні вершини в них містять однакову інформацію.