Обход дерева без рекурсии

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

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

Например, у нас есть дерево, где одному руководителю назначается несколько сотрудников, а в результате мы хотим получить плоскую таблицу, в которой будут: Руководитель, его Сотрудник, Уровень руководителя и Уровень сотрудника. В этом случае код будет следующий:

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

				Если Родитель = Неопределено И СтрДерева.Родитель = Неопределено Тогда
					НоваяСтрока = ТаблицаИерархии.Добавить();
					НоваяСтрока.УровеньРуководителя = 0;
					НоваяСтрока.УровеньСотрудника = 0;
					НоваяСтрока.Сотрудник = СтрДерева.Сотрудник;
					НоваяСтрока.Руководитель = Справочники.Сотрудники.ПустаяСсылка();
				КонецЕсли;
				
			КонецЕсли;

			// Тут делаем псевдо рекурсию
			Для Каждого СтрДереваНовый Из СтрДерева.Строки Цикл
				МассивСтрокНовый.Добавить(СтрДереваНовый);
			КонецЦикла;
		КонецЦикла;
		
		МассивСтрок = Новый Массив;
		Для Каждого СтрДерева Из МассивСтрокНовый Цикл
			МассивСтрок.Добавить(СтрДерева);
		КонецЦикла;
	КонецЦикла;
	
	Возврат ТаблицаИерархии;
	
КонецФункции

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

Полезные материалы

Вывод дерева в табличный документ СКД (первый комментарий)
Поиск в ширину
Поиск в глубину