Теоретична частина. Бінарне дерево – це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: в лівому піддереві

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

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

Для того щоб відобразити Бінарне дерево на екрані, спочатку слід перевірити чи взагалі воно існує. Якщо ми не заповнимо дерево і не закладемо насіннячко (не створимо корінь), то дерева в принципі існувати не може і тому відображати буде нічого, але якщо створити, то використовуючи рекурсивний виклик функції послідовно відображаємо всі елементи. Крім того, ця перша перевірка буде і сигналом для завершення рекурсивного виклику функції. Адже якщо зустрінеться Нульова ланка, то відбувається return, а ми після створення кожної ланки очищали пам'ять для наступного зростання.

Двійкове дерево задається наступною структурою:

typedef struct _t {

int data; /* данные в узле */

struct _t *left, *right; /* указатели на левого и правого сыновей */

} t;

t *root; /* корень дерева */

Таким чином, кожен елемент дерева містить деякі дані і два покажчика на нащадків (на лівого сина і на правого). Сам вузол будемо називати батьком цих двох нащадків. Визначення дерева вимагає, щоб у кожного вузла, крім кореня, був рівно один батько. Покажчик на корінь дерева зберігається у змінній root, вона дорівнює нулю, якщо дерево порожньо.

Лівим і правим піддеревами вузла t (t! = 0) будемо називати дерева (можливо, порожні), корінням яких є відповідно t-> left і t-> right.

Основні операції на деревах: пошук елемента, додавання елемента, видалення елемента. Для пошуку елемента в довільному бінарному дереві необхідно обійти всі елементи цього дерева. Існує два основних способи обходу дерева: в глибину і в ширину.