Під прошивкою дерева розуміється заміна за певним правилом порожніх покажчиків на синів покажчиками на наступні вузли, відповідні обходу.
Оскільки після прошивання дерева поля left і right можуть характеризувати або структурні зв'язки, або "нитки", виникає необхідність розрізняти їх, для цього вводяться в опис структури дерева характеристики лівого і правого покажчиків (FALSE і TRUE).
Таким чином, прошиті дерева швидше обходяться і не вимагають для цього додаткової пам'яті (стек), однак вимагають додаткової пам'яті для зберігання прапорів ниток, а також ускладнені операції включення та видалення елементів дерева.
Прошита бінарне дерево на Паскалі можна описати таким чином:
де lf і rf - вказують, чи є зв'язок покажчиком на елемент або ниткою. Якщо lf або rf одно FALSE, то зв'язка є ниткою.
До створення дерева головний вершина має наступний вигляд: Тут пунктирна стрілка визначає зв'язок по нитці. Дерево підшивається до лівої галузі.
У програмному прикладі 6.14 приведена функція (Inson) для визначення сина (наступника) даної вершини.
(* ------ Функція, що знаходить наступника даної вершини X ---- *)
(* -------- відповідно зі змішаним обходом ------------ *)
Funtion Inson (x: TreePtr): TreePtr;
У програмному прикладі 6.15 приведена функція (Int) для визначення батька (предка) даної вершини.
(* ---------- Функція, що видає попередника вузла ------ *)
(* ------- відповідно до смеш1анним обходом ------------ *)
Function Inp (x: TreePtr): TreePtr;
if not (x ^ .lf) then exit;
while Inp ^ .rf do Inp: = Inp ^ .right; <связка не нить>
У програмному прикладі 6.16 приведена функція, що реалізує алгоритм включення запису в прошита дерево (leftIn). Цей алгоритм вставляє вершину P в якості лівого піддерева заданої вершини X в разі, якщо вершина X не має лівого піддерева. В іншому випадку нова вершина вставляється між вершиною X і вершиною X ^ .left. При цій операції підтримується правильна структура прошивки дерева, відповідна змішаного обходу.
(* - Вставка p зліва від x або між x і його лівій вершиною - *)
Procedure LeftIn (x, p: TreePtr);
p ^ .left: = x ^ .left; p ^ .lf: = x ^ .lf; x ^ .left: = p;
x ^ .lf: = TRUE; p ^ .right: = x; p ^ .rf: = FALSE;
(* -------- Перевстановлення зв'язку з попередником -------- *)
begin q: = TreePtr (Inp (p)); q ^ .right: = p; q ^ .rf: = FALSE;
Для прикладу розглянемо прошивку дерева наведеного на ріс.6.20. при низхідному обході.
Машинне подання дерева при низхідному обході з прошивкою наведено на ріс.6.28.
Мал. 6.28. Машинне чіткий уявлення вихідного дерева, представленого на ріс.6.20 при низхідному обході з прошивкою
Трасування спадного обходу з прошивкою приведена в табл.6.3.
Розглянемо на прикладі того ж дерева прошивку при змішаному обході. Машинне подання дерева при змішаному обході з прошивкою наведено на ріс.6.28.