Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Прошитые деревья




Читайте также:
  1. Б-деревья. Определение Алгоритмы поиска, включения и исключения. Необходимость их применения.
  2. Древовидные структуры (деревья бинарные, сбалансированные, сильноветвящиеся). Основные операции (поиск, вставка, удаление).
  3. Оптимальные деревья поиска. Эффективность их применения. Алгоритм построения оптимального дерева поиска.
  4. Синтаксические деревья

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

 
 

 


Если мы воспользуемся прошитым бинарным деревом, то вид узла для него будет таким

:

 

 

Один из возможных способов прошивки бинарного дерева заключается в том, что для каждого узла, не имеющего левого поддерева, запоминается ссылка на непосредственного предшественника, а для каждого узла, не имеющего правого поддерева ,запоминается ссылка на его непосредственного преемника. Предшественников и преемников для узла определяют исходя из списка, который получается при прохождении рассматриваемого бинарного дерева в симметричном порядке. Для того, чтобы отличать ссылку на левого или правого сына (такие ссылки называют структурными связями) от ссылки на предшественника или преемника узла (такие ссылки называют “нитями”), используются индикаторные поля LP и RP.

Симметричным прохождением бинарного дерева является такое прохождение, когда мы проходим сначала левое поддерево, затем посещаем корень и последним посещаем правое поддерево: A R B.

 
 

 


В памяти это дерево будет выглядеть так:
Пример. Рассмотрим бинарное дерево:

           
   
   
 
 
При его симметричном прохождении получаем следующий список вершин: c, b, a, d, g, e, f.
 

 

 


Использование “прошивок” существенно убыстряет прохождение дерева, позволяет не использовать стек, но при этом усложняются алгоритмы включения / исключения узла, т.к. в прошитом дереве необходимо управлять не только структурными связями, но и “нитями”.

 


Дата добавления: 2015-04-18; просмотров: 22; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты