Как обойти дерево значений

Введение

Для начала, чтобы было максимально понятно, о чем пойдет речь, дадим определение, что такое дерево значений?

Дерево значений - это иерархическая структура. Дерево значений отображает группировки, заданные программистом. 

Подобные группировки можно встретить в отчетах на СКД. 

Группы можно свернуть, развернуть нажав на + или -. Задать по ним итоги (как ресурсы в СКД).

Вот как звучит определение в справочной информации 1С:

Описание:

Используется для доступа к свойствам и методам дерева значений в целом.

Объект, представляющий собой древовидную структуру, обладает сходной функциональностью с таблицей значений, а также обладает возможностью добавлять подчиненные строки к какой-либо строке дерева.

Внимание! В толстом клиенте (обычное приложение) передача значений данного типа с клиента на сервер и обратно приводит к возникновению исключения.

Доступность: 

Сервер, толстый клиент, внешнее соединение, мобильное приложение (сервер), мобильный автономный сервер. 

Сериализуется. Данный объект может быть сериализован в/из XDTO. Тип XDTO, соответствующий данному объекту, определяется в пространстве имен {http://v8.1c.ru/8.1/data/core}. Имя типа XDTO: ValueTree.

Как создать дерево значений на форме 

Самый простой способ создать его на форме, нажав создать реквизит  и задать тип в свойствах "ДеревоЗначений".  И поместить созданное дерево значений на форму.

Способ сложнее: создать объект "ДеревоЗначений" и связать его с созданным элементом и разместить его на форме.(Рассматривать пока не будем)

Как обойти дерево значений

Чтобы обойти дерево значений, можно использовать следующий код:

&НаСервере
Процедура ОбойтиРекурсивноСтрокиДерева(Выборка)
	Пока Выборка.Следующий() Цикл
		
		ПодчиненныеСтроки  = Выборка.Выбрать();
		
		Если ПодчиненныеСтроки.Количество() > 0 Тогда  
			СтрокаЗаполняемогоДереваПодчиненный = СтрокаЗаполняемогоДерева.ПолучитьЭлементы();
			ОбойтиРекурсивноСтрокиДерева(ПодчиненныеСтроки,СтрокаЗаполняемогоДереваПодчиненный);
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры

В переменную "Выборка" может передаваться иерархический запрос, дерево значений, либо ветка дерева.

Выборка например может собираться по такому шаблону:

ВашЗапрос = Новый Запрос; 
	
ВашЗапрос.Текст = 
"ВЫБРАТЬ
|	ВашРегистр.Поле1 КАК Поле1,
|	ВашРегистр.Поле2 КАК Поле2,
|	ВашРегистр.Поле3 КАК Поле3
|ИЗ
|	РегистрСведений.ВашРегистр КАК ВашРегистр
|
|УПОРЯДОЧИТЬ ПО
|	Поле1
|ИТОГИ
|	СУММА(Поле2),
|	СУММА(Поле3)
|ПО
|	Поле1"; 

Выборка = ВашЗапрос.Выполнить().Выбрать(ОбходРезультатаЗапроса.ПоГруппировкамСИерархией);

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

Дерево = новый ДеревоЗначений;
	
// Добавляем колонки
Дерево.Колонки.Добавить("Наименование", Новый ОписаниеТипов("Строка"), "Название", 100);
Дерево.Колонки.Добавить("Сумма", Новый ОписаниеТипов("Число"), "Сумма", 10);
// Особое внимание: колонка "Родитель" должна иметь тип "Дерево значений.Строка дерева значений"
Дерево.Колонки.Добавить("Родитель", Новый ОписаниеТипов("ДеревоЗначений.СтрокаДереваЗначений"), "Родитель", 10);
	
	

Либо можно воспользоваться примером создания из справки 1С:

ДеревоРезультатов = Новый ДеревоЗначений;
Для Каждого Колонка ИЗ ТаблицаРезультатов.Колонки Цикл
    ДеревоРезультатов.Колонки.Добавить(Колонка.Имя);
КонецЦикла;

Ветка дерева - это группировка дерева, которая также имеет тип "ДеревоЗначений". Например, это может быть родитель.

А теперь разберем код обхода для дерева значений.

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

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

Первым делом мы обрабатываем первую строку, получив предварительно дерево значений. 

Далее снова получаем из дерева значений дерево значений (с помощью строки: СтрокаЗаполняемогоДереваПодчиненный = СтрокаЗаполняемогоДерева.ПолучитьЭлементы()),  вызываем этот же метод, передав в него полученное дерево.

Важно в этом алгоритме проверять наличие подчиненных строк, например с помощью условия:

Если ПодчиненныеСтроки.Количество() > 0 Тогда  
    СтрокаЗаполняемогоДереваПодчиненный = СтрокаЗаполняемогоДерева.ПолучитьЭлементы();
	ОбойтиРекурсивноСтрокиДерева(ПодчиненныеСтроки,СтрокаЗаполняемогоДереваПодчиненный);
КонецЕсли;

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

Также при обходе дерева значений можно заполнять другое дерево значений. Это можно сделать например, вот так:

Процедура ОбойтиРекурсивноСтрокиДерева(Выборка, ЗаполняемоеДерево)
	Пока Выборка.Следующий() Цикл
		
		СтрокаЗаполняемогоДерева = ЗаполняемоеДерево.Добавить();	
		
		ЗаполнитьЗначенияСвойств(СтрокаЗаполняемогоДерева, Выборка);
		
		ПодчиненныеСтроки  = Выборка.Выбрать();
		
		Если ПодчиненныеСтроки.Количество() > 0 Тогда  
			СтрокаЗаполняемогоДереваПодчиненный = СтрокаЗаполняемогоДерева.ПолучитьЭлементы();
			ОбойтиРекурсивноСтрокиДерева(ПодчиненныеСтроки,СтрокаЗаполняемогоДереваПодчиненный);
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры

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

Также важно при заполнении дерева чтобы колонки одного дерева совпадали с колонками другого дерева, иначе дерево останется пустым.

Также при работе с деревом может потребоваться получить самый низкий его уровень. Это можно сделать, например, так:

Функция ПолучитьМассивСамыхМладшихДетейДерева(СтрокиДерева, МассивВывода)  
	
	Для каждого элемента  Из СтрокиДерева Цикл
		ВложенныеСтроки = элемента.ПолучитьЭлементы();  
		Если ВложенныеСтроки.Количество() > 0 Тогда                   	
			ПолучитьМассивСамыхМладшихДетейДерева(ВложенныеСтроки, МассивВывода); 
		Иначе
			Если элемента.Выбрать Тогда
				
				МассивВывода.Добавить(элемента);	
				
			КонецЕсли;
			
		КонецЕсли;
	КонецЦикла; 
	
	Возврат МассивВывода;
КонецФункции

Такой же алгоритм, что и при обходе дерева, только в добавок к этому еще происходит сбор элементов самого нижнего уровня.

Чтобы свернуть либо развернуть дерево значений, также необходимо воспользоваться рекурсией, например, вот так для того, чтобы свернуть:

Процедура СвернутьДерево (ЭлементыДерева)
        	Для Каждого элемент Из ЭлементыДерева Цикл
        		ЭлементыЭлемента = элемент.ПолучитьЭлементы();
                    	Если ЭлементыЭлемента.Количество() > 0 тогда
                               	СвернутьДерево(ЭлементыЭлемента);        	 
                    	КонецЕсли;
                    	Элементы.Дерево.Свернуть(элемент.ПолучитьИдентификатор());
        	КонецЦикла;
КонецПроцедуры

И напоследок немного о рекурсии.

Что такое рекурсия?

Рекурсия — это способ организации алгоритма, при котором функция (или процедура) вызывает саму себя прямо или косвенно.

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

Классический пример — вычисление факториала, обход файловой системы или, как в нашем случае, обход иерархического дерева значений.

В платформе 1С:Предприятие рекурсия реализуется через вызов процедуры или функции из её же тела.

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

Плюсы использования рекурсии

1. Естественность для иерархий
   Дерево значений по своей природе рекурсивно: каждая ветка содержит подветки такой же структуры. Рекурсивный код идеально ложится на эту модель — он повторяет логику «спуститься вниз, обработать, вернуться». Читать и поддерживать такой код проще, чем реализовывать обход с помощью явных стеков и очередей.

2. Краткость и выразительность
   Рекурсивный алгоритм обычно занимает в 2–3 раза меньше строк, чем итеративный аналог. Например, обход всех уровней дерева укладывается в 10–15 строк кода, тогда как ручное управление стеком раздувает реализацию до 30–40 строк с множеством вспомогательных переменных.

3. Удобство работы с разной глубиной
   Глубина вложенности может быть произвольной — рекурсия автоматически адаптируется. Не нужно заранее знать максимальный уровень, в отличие от вложенных циклов, где количество уровней должно быть фиксировано.

4. Наглядная обработка «листьев»
   Когда нужно выполнить действие только на самых нижних узлах (например, собрать конечные элементы), рекурсия позволяет проверить наличие потомков и обработать только терминальные строки, как в приведённой в статье функции ПолучитьМассивСамыхМладшихДетейДерева.

5. Простота реализации отката (backtracking)
   Если в процессе обхода нужно принять решение на основе данных из родителей (накопить сумму, построить путь), рекурсия позволяет легко передавать накопленный результат вниз по цепочке вызовов, а затем возвращать его обратно.

Минусы и подводные камни

1. Ограничение по глубине стека
   В 1С глубина рекурсии ограничена ёмкостью стека вызовов. На практике безопасным считается не более 100–150 вложенных вызовов (точное значение зависит от версии платформы и объёма локальных переменных). Если дерево имеет 200 уровней, рекурсивный обход вызовет ошибку «Переполнение стека» (или «Слишком много вложенных вызовов»). В обычных бизнес-задачах такая глубина встречается редко, но в справочниках с глубокой вложенностью (например, классификатор ОКВЭД) это может стать проблемой.

2. Низкая производительность на больших объёмах
   Каждый рекурсивный вызов — это накладные расходы: создание нового контекста, сохранение и восстановление регистров, проверка условий. Для дерева с десятками тысяч строк и средней глубиной 5–7 уровней рекурсия работает приемлемо, но при сотнях тысяч строк время выполнения может оказаться неприемлемо большим. Итеративный обход с использованием коллекции в качестве стека часто оказывается быстрее из-за меньшего числа переходов управления.

3. Сложность отладки
   Отладить рекурсивную функцию сложнее, чем линейный код. При пошаговом выполнении вы прыгаете вглубь вызовов, трудно отследить, на каком уровне и с какими данными происходит ошибка. Стек вызовов в 1С не всегда информативен, и локализация проблемы может занять время.

4. Риск бесконечной рекурсии
   Если забыть проверить условие выхода (например, наличие подчинённых строк), функция будет вызывать себя бесконечно, пока не упадёт с ошибкой стека. Это одна из самых частых оплошностей при написании рекурсивных процедур. В статье подчёркивается необходимость проверки ПодчиненныеСтроки.Количество() > 0.

5. Трудоёмкая оптимизация
   Рекурсивный код сложно распараллелить или оптимизировать через индексы — он последователен. Для ускорения часто приходится переписывать его в итеративный вариант, что требует дополнительных усилий.

6. Проблемы с большими данными на клиенте
   Если рекурсивный обход выполняется на клиентской стороне (в форме), это может «заморозить» интерфейс, так как все вызовы происходят в одном потоке. Рекомендуется всегда переносить тяжёлые рекурсивные операции на сервер.

Итог

Рекурсия — мощный и красивый инструмент для работы с иерархиями, особенно в 1С, где деревья значений встречаются повсеместно. Её главное преимущество — прямое соответствие структуре данных и минималистичный код. Однако использовать её нужно с осторожностью, контролируя глубину и объём обрабатываемых данных. Для большинства типовых задач (отчёты с 2–5 уровнями группировок) рекурсия идеальна. А если дерево разрастается или становится слишком глубоким — стоит перейти к итеративным методам или оптимизировать запрос.