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

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

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

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

Рис.5.3. Різні позиційні, але однаково впорядковані бінарні дерева

У позиційному бінарному дереві кожна вершина може бути єдиним способом описана за допомогою рядка символів над алфавітом {0, 1}. Це дає значну зручність для зображення дерев в пам‘яті комп‘ютера. При цьому корінь дерева характеризується рядком "0". Всякий син вершини Z характеризується рядком, префікс (початкова частина) якого є рядком, що характеризує Z. Рядок, приписаний будь-якій висячій вершині Z, не є префіксом ні для яких рядків, що характеризують інші вершини дерева. Множина рядків, що відповідає висячим вершинам деякого дерева, утворює префіксний код цього дерева (рис.5.4). Довжина рядка, що відповідає вершині, дорівнює рівню цієї вершини.

Рис. 5.4. Символьний опис дерева

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