В прошлой статье
мы изучили, как выглядят деревья в программировании и как обойти дерево.
Для задания дерева достаточно в каждом узле дерева хранить либо список дочерних объектов, либо ссылку на родительский. Если есть что-то одно, то можно найти и второе.
По списку дочерних объектов найдём ссылки на родительские
У нас уже есть класс Organization (организация), и каждая организация содержит в себе список дочерних Childes:
Также у организации есть Id родительской - ParentId. Сейчас он не используется и потому горит серым.
Из прошлой статьи у нас также остался пример организаций
и код для обхода дерева в OrganizationTreeWalker.Apply():
Сделаем аналогичный обход дерева, но с заполнением ParentId. То есть, по Childes мы будем узнавать ParentId. Назовём метод FillParentId(). Сначала он будет вызываться для корневой организации. Далее он будет проходить по всем дочерним организациям и устанавливать у них ParentId равный Id корневой организации. При этом метод будет вызывать сам себя для каждой корневой организации, чтобы рекурсивно заполнить ParentId и у них:
Вызовем этот метод и передадим туда корневую организацию:
Посмотрим дерево в отладке, наведя мышку на organizationTree после того, как отработает наш метод. А чтобы программа не закончилась, добавим после вызова нашего метода какую-нибудь печать:
Получится:
Найдём глубину дерева
Глубиной дерева называют максимальное количество узлов на пути от корня до листьев (включая корень и листья). Корень - узел, который не имеет родителя. Листья - это узлы дерева, которые не имеют дочерних.
Пусть нам дано дерево, глубину которого нужно найти. Сначала посмотрим на корень дерева. Глубина дерева равна максимальной глубине ветвей, выходящих из корня, плюс 1 (сам корень). Глубина каждой ветви равна максимальной глубине её подветвей плюс 1. Глубина каждой подветви равна максимальной глубине её подподветвей плюс 1, и так далее. Наконец, мы приходим к листьям. Очевидно, глубина листа равна 1.
Вот алгоритм:
Сначала мы проверяем, лист ли это. Если это лист, то глубина равна 1, мы сразу выдаём это в ответ. Иначе у узла есть дочерние ветви. Мы рекурсивно запускаем поиск глубины для каждой из дочерних ветвей. Метод Select() заменяет каждую ветвь на её длину. Получается IEnumerable<int> из длин дочерних ветвей. Мы выбираем максимальную из них с помощью метода Max() и прибавляем к ней 1, что и выдаём в ответ.
Проверим:
Чтобы лучше протестировать новый метод, нужно запустить его на разных исходных данных. В том числе обязательно протестировать крайние случаи - когда всё дерево состоит из одного узла.
Далее
Часть 3:
Оглавление: