2

Если можете, то так же приведите примеры.

3
  • Честно говоря, впервые услышал от вас такой термин. С одной стороны, материал по теме легко ищется, но я не знаю, стоит ли его писать как "ответ" (и вообще праивльный ли это ответ) khpi-iip.mipk.kharkiv.edu/library/datastr/book/prt06.html
    – Lol4t0
    Commented 18 апр. 2015 в 19:04
  • 1
    @Lol4t0, думаю можете сделать ответом. Ведь в этом материале есть довольно подробный раздел ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ (и даже с массой картинок)
    – avp
    Commented 18 апр. 2015 в 19:13
  • Хм, из Германии не открывает: ошибка DNS o_O
    – VladD
    Commented 18 апр. 2015 в 19:26

2 ответа 2

6

По материалам учебного пособия МОДЕЛИ И CСТРУКТУРЫ ДАННЫХ (ХГПУ)

Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу.

Прошивка делается для того, чтобы ускорить проход по дереву, переходя от листьев сразу на следующие по правилу обхода вершины.

Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много нулевых указателей. Действительно в дереве с N вершинами имеется ( N+1 ) нулевых указателей. Это незанятое пространство можно использовать для изменения представления деревьев. Пустые указатели заменяются указателями - "нитями", которые адресуют вершины дерева, и расположенные выше. При этом дерево прошивается с учетом определенного способа обхода. Например, если в поле left некоторой вершины P стоит нулевой укзаатель, то его можно заменить на адрес, указывающий на предшественника P, в соответствии с тем порядком обхода, для которого прошивается дерево. Аналогично, если поле right пусто, то указывается преемник P в соответствии с порядком обхода. Поскольку после прошивания дерева поля left и right могут характеризовать либо структурные связи, либо "нити", возникает необходимость различать их, для этого вводятся в описание структуры дерева характеристики левого и правого указателей (FALSE и TRUE).

Таким образом, прошитые деревья быстрее обходятся и не требуют для этого дополнительной памяти (стек), однако требуют дополнительной памяти для хранения флагов нитей, а также усложнены операции включения и удаления элементов дерева.

Ячейка прошитого дерева имеет вид

struct node
{
    data_type_t dat;
    node *left, *right; //теперь left и right могут указывать как на дочерние элементы, так и содержать нитки, ведущие на другие уровни
    bool left_is_thread, right_is_thread;
}

Прошитое дерево может выглядеть, например, следующим образом (нити показаны пунктиром)

СС МОДЕЛИ И CСТРУКТУРЫ ДАННЫХ (ХГПУ)

3

Прошитое бинарное дерево, согласно Библии (TAOCP 2.3.1) — дерево, в котором в узлах есть специальные дополнительные связи («прошивка»), указывающие на предыдущий/следующий узел в симметричном прохождении дерева. Расстановка таких связей позволяет обходить дерево в прямом/симметричном/концевом порядке без дополнительного стека. Поскольку прошивка нужна лишь для узлов, не имеющих одного или обоих потомков, на самом деле они требуют всего лишь 2 бита дополнительной памяти в каждом из узлов.

2
  • Как оно по английски называется?
    – Lol4t0
    Commented 18 апр. 2015 в 19:36
  • 1
    @Lol4t0: Threaded binary tree.
    – VladD
    Commented 18 апр. 2015 в 19:40

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.