1
УДК 004.022
Построение двоичного дерева на основе модифициро-
ванной схемы хранения деревьев общего вида
«left child» — «right sibling» (LCRS)
© Н.С. Гриценко, Ю.С. Белов
КФ МГТУ им. Н.Э. Баумана, Калуга, 248000, Россия
Рассмотрены схема хранения деревьев с произвольным ветвление «left child» — «right
sibling» (LCRS) и модифицированная схема LCRS для построения двоичного дерева.
Приведены алгоритмы создания дерева с порядком на «детях», добавления узла
в модифицированную схему LCRS и подсчета числа узлов двоичного дерева LCRS.
Ключевые слова:
типы данных, структуры данных, графы, деревья, двоичные де-
ревья.
Одной из наиболее распространенных структур данных являются
деревья. Их применяют для решения широкого круга задач: хране-
ния, поиска и сортировки информации, в качестве элементов экс-
пертных систем, для определения скрытых поверхностей, при отсе-
чении невидимых частей ландшафта и трассировки лучей, в процессе
создания баз данных, а также для организации доступа к простран-
ственным данным, т. е. для индексации многомерной информации,
такой, например, как географические данные с двумерными коорди-
натами (широтой и долготой). Особое место среди всех занимают
двоичные. Частое использование их в прикладных задачах привело к
необходимости создания механизма преобразования любого дерева в
двоичное. Одним из вариантов решения данной проблемы является
схема хранения дерева, или «левый ребенок» — «правый сосед»
(«left child» — «right sibling» (LCRS)) (рис. 1), которую применяют
для деревьев с произвольным ветвлением.
Для осуществления перехода от дерева с произвольным ветвле-
нием к двоичному в рамках данного механизма необходимо совер-
шить следующие преобразования: «левый ребенок» каждой вершины
остается тем же; «правым ребенком» становится «правый сосед»
данной вершины (т. е. элемент, являющийся следующим «ребенком»
одного и того же «родителя»). В результате получается дерево, каж-
дый узел которого имеет не более двух «потомков».
Кроме осуществления перехода от дерева произвольного типа к
двоичному схема LCRS после определенной модификации может
также являться самостоятельным двоичным деревом [1]. Использо-
вание данной схемы оправданно в случае, когда возникает необходи-
мость часто решать такие локальные задачи, как вывод элементов
