У бінарному дереві, що містить N вузлів, на кожен вузол, крім кореня вказує рівно одна зв'язок. Всього зв'язків 2 * N; непустих - N-1. отже, N + 1 зв'язок порожня. Порожні зв'язки існують тільки для того, щоб позначити, що далі в цьому напрямку шляху немає, для чого достатньо одного біта. Виникає питання: а чи не можна більш раціонально використовувати простір, займане порожніми зв'язками. Прошиті дерева використовують місце, займане порожніми зв'язками для зберігання покажчиків, що спрощують проходження дерева. Ці додаткові зв'язку називають нитками. звідки і з'явився термін прошиті. Введемо позначення:
- * P - попередник вузла P в зворотному порядку,
- P * - послідовник вузла P в зворотному порядку,
- + P - попередник в прямому порядку,
- P + - послідовник в прямому порядку.
Дерево може бути прошито для обходу в одному з порядків. Порівняємо звичайне дерево і дерево, прошита для обходу в зворотному порядку. Замість порожніх лівих зв'язків будемо зберігати покажчик на попередника в зворотному порядку, замість порожніх правих зв'язків - покажчик на послідовника. Ці зв'язки будемо називати "нитками" на відміну від основних зв'язків, які такі ж, як в звичайному дереві. Для того, щоб відрізняти основні зв'язку від ниток, в кожному вузлі заведемо два поля L і R. які матимуть значення THREAD. якщо зв'язок - нитка і MAINLINK. якщо зв'язок - основна (THREAD і MAINLINK - константи). Таким чином, структура вузла прошитого дерева має вигляд:
На рис.25 зображено прошита дерево. Пунктиром зображені нитки.
Рис.25. прошита дерево
Перевага прошитих дерев полягає в тому, що спрощуються алгоритми обходу. Нижче приведена функція, яка повертає покажчик на послідовника p в зворотному порядку.
if (p-> R == THREAD) return q; // якщо це нитка, то q-результат
// в іншому випадку спуститися до упору по лівим зв'язків
При наявності алгоритму визначення послідовника відпадає необхідність в стеці (явному чи породжується механізмом реалізації рекурсії). Функція, що виконує обхід дерева в зворотному порядку набуває вигляду:
void InverseBypass (NODE * Root)
// знайдемо перший в зворотному порядку вузол
// він знаходиться в кінці спуску по основним лівим зв'язків
// проходимо всі вузли, використовуючи функцію NextUzel