ЦОНТ НИИСИ РАН
Софт. Программы для компьютера. Для пк

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

Прошивка бинарного дерево

Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много указателей типа NIL. Это незанятое пространство можно использовать для изменения представления деревьев. Пустые указатели заменяются указателями - "нитями", которые адресуют вершины дерева, и расположенные выше. При этом дерево прошивается с учетом определенного способа обхода.

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

Таким образом, прошитые деревья быстрее обходятся и не требуют для этого дополнительной памяти стек , однако требуют дополнительной памяти для хранения флагов нитей, а также усложнены операции включения и удаления элементов дерева. Если lf или rf равно FALSE, то связка является нитью. До создания дерева головная вершина имеет следующий вид: Здесь пунктирная стрелка определяет связь по нити. Дерево подшивается к левой ветви.

Дерево с прошивкой

Этот алгоритм вставляет вершину P в качестве левого поддерева заданной вершины X в случае, если вершина X не имеет левого поддерева. При этой операции поддерживается правильная структура прошивки дерева, соответствующая смешанному обходу.

Дерево с прошивкой

Машинное связное представление исходного дерева, представленного на рис. Рассмотрим на примере того же дерева прошивку при смешанном обходе. Машинное представление дерева при смешанном обходе с прошивкой приведено на рис. Машинное связное представление дерева при смешанном обходе с прошивкой. Главная Случайная страница Контакты Заказать. Предыдущая Следующая. Прошитое бинарное дерево на Паскале можно описать следующим образом: ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ Предыдущая Следующая Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу.

Машинное представление дерева при нисходящем обходе с прошивкой приведено на рис.

Опубликовано в рубрике Драйвера ga
Twitter Delicious Facebook Digg Stumbleupon Favorites More
  • Прикрепленное видео

Все права защищены. © 2001 toozza.ru