У разі подання бінарного дерева у вигляді вузлів, що містять інформаційне поле і два поля зв'язку, кількість полів зв'язку, що мають значення nil. завжди більше числа зв'язків, що вказують на реально існуючі вузли. Тому часто такий спосіб зберігання дерев виявляється неефективним з точки зору використання пам'яті, особливо, якщо розмір інформаційного поля можна порівняти з розміром покажчика.
Мал. 6.1 - Симетрично прошита справа бінарне дерево
Оскільки потрібно якимось чином відрізняти звичайну зв'язок від прошивочно нитки, кожному вузлу додається два однобітових (логічних) поля тега: ltag і rtag. Якщо значення тега true. відповідне поле зв'язку є звичайною зв'язком, в разі значення false - прошивочно ниткою.
У зв'язку з цим вузол звичайного бінарного дерева представляється структурою
Вузол прошитого бінарного дерева має іншу структуру
Логічні поля в прошитому дереві можуть набувати наступних значень.
1. ltag = true. отже, left являє собою звичайну зв'язок.
2. ltag = false. отже, left вказує на вузол-попередник.
3. rtag = true. отже, right являє собою звичайну зв'язок.
4. rtag = false. отже, right вказує на вузол-наступник.
Розглянемо вставку нової вершини зліва від заданої в симетрично прошита бінарне дерево (рис. 6.2). На рис. 6.3 показано результуюче дерево.
Мал. 6.2 - Початкове симетрично прошита дерево
Мал. 5 - прошиті дерево після вставки в нього нового елемента
Тут потрібно вставити вершину I в як лівого піддерева вершини А. якщо А не має лівого піддерева. В іншому випадку нова вершина вставляється між А і її лівим сином.
Для зручності створення і обходу дерева використовується додатковий головний вершина Head. яка служить при симетричному обході попередником його першої вершини і приймачем всіх його кінцевих вершин.
Поряд з перевагами прошитих дерев: швидкий обхід, відсутність необхідності в стеці, можна визначити попередника і наступника вершини, існують недоліки. Включення нової вершини в дерево займає більше часу, тому що необхідно підтримувати два типи зв'язків: структурні і по нитках. Тому прошиті дерева доцільно використовувати в тих завданнях, де зміни в деревах відбуваються рідко, а обходи виконується часто.