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