Деревья в программировании
В программировании часто возникают древовидные структуры данных, так что нужно уметь с ними работать. Например, организации и подразделения - одна организация может содержать несколько дочерних организаций и подразделений, те в свою очередь могут содержать ещё дочерние организации и так далее:
Каждая организация хранит в себе список дочерних организаций или ссылку на родительскую - таким образом, во всех задачах, где объект должен хранить список дочерних объектов или ссылку на родительский объект возникает дерево.
Создадим пример дерева. Для этого создадим папку Trees и создадим в ней файл Organization.cs:
Теперь в файле Program.cs создадим корневой объект и вложенные в него объекты:
Отформатируйте код автоматически (Ctrl + Alt + L в Rider). Отступы отражают глубину вложенности элементов дерева.
Посмотрим, какое дерево получилось, в отладке. Но сейчас команда создать переменную organizationTree является последней. Это значит, что если она будет выполнена, программа автоматически завершится и мы не сможем посмотреть её результат. Чтобы этого не произошло, добавим после неё команду печати в консоль чего-нибудь и поставим точку остановки на эту команду:
Запустим программу в режиме отладки, то есть, на жучка. Когда выполнение дойдёт до точки остановки, программа остановится и перейдёт в режим отладки. Наведём мышку на переменную organizationTree, чтобы посмотреть, что хранится внутри неё:
Раскроем всплывающую подсказку:
Мы видим корневую организацию. У неё есть 2 дочерних, которые лежат в списке Childes. Раскроем его:
Корневой организации подчинены два отделения - Орловское и Курское. Внутри Орловского отделения есть 2 отдела:
Рекурсивный обход дерева
Создадим функцию, которая будет обходить все элементы дерева и применять к ним какое-нибудь действие action(). Расположим эту функцию в статическом классе OrganizationTreeWalker:
Метод Apply() получает на вход самую корневую организацию и действие, которое надо будет сделать над каждой организацией. Действие может быть любым, то есть, это будет функция. Эта функция должна знать о текущей организации, чтобы что-нибудь сделать с ней. Поэтому она принимает на вход 1 аргумент типа Organization. Действие ничего не возвращает в ответ. Поэтому тип данных такой функции - Action<Organization>. Например, распечатаем Id и Name каждой организации:
Здесь красным обведён первый аргумент метода Apply() (корневая организация), а жёлтым - второй (функция обработки каждого элемента).
Первым делом метод Apply() вызывает действие у корневой организации. Затем он обходит все дочерние организации и у каждой из них вызывает самого себя, чтобы обработать их. Дальше у каждой из них он выполняет действие и снова вызывает самого себя, чтобы обработать их дочерние организации, и так далее. Когда метод вызывает сам себя, это называется рекурсией. Рекурсия отражается на полях специальным значком (строка 12).
Проще увидеть всё в отладке. Снимем прошлую точку остановки и поставим новую на вызов метода Apply():
Когда выполнение дойдёт до точки остановки, нажмём "Шаг внутрь" Step Into:
Мы окажемся внутри метода Apply. Наведём мышку на переменную organization - в ней сейчас лежит корневая корпорация:
Жёлтая стрелка на полях показывает, какая команда будет выполняться следующей. Сейчас это фигурная скобка, потому что мы только что зашли в метод. Сделаем несколько шагов Step Over до вызова Apply:
Здесь вызывается Apply для child, то есть, для дочернего подразделения. Сделаем шаг внутрь. Мы снова окажемся на входе в Apply. При этом organization будет хранить "Орловское региональное подразделение":
Обратите внимание, что первый вызов Apply ещё не закончился, а мы уже смотрим второй вызов. Стек вызовов подтверждает это:
Снова сделаем несколько шагов. Вызовется действие для "Орловского регионального подразделения", а затем мы войдём в цикл по дочерним организациям. Для каждой дочерней организации снова будет вызван Apply(). Зайдём внутрь. На сей раз organization будет хранить "Отдел по продажам":
Стек увеличится:
Щёлкая на элементах стека, мы можем посмотреть, что было на тех уровнях вложенности. Мы видим, что самый первый Apply() ещё не закончился. Он ждёт конца второго, а второй ждёт конца третьего. Проделав все шаги в третьем, мы выйдем из него и окажемся во втором. Второй вызовет Apply() ещё раз для "Научного отдела". Когда он завершится, мы снова вернёмся во второй. Проделав все шаги во втором, мы вернёмся в первый. Первый обработает "Курское региональное отделение" и на этом всё завершится. Итак, каждый раз Apply() вызывается для обработки текущего подразделения, и при необходимости он вызывает вложенный Apply() для вложенных в него подразделений. Сколько бы ни было уровней вложенности у подразделений - мы не выйдем из корневого Apply(), пока не обойдём все их.
Далее
Деревья и рекурсия (часть 2)
Оглавление