0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется<strong>обходом дерева</strong>. Подразумевается, что в процессе обхода каждый узел будет затронут только один раз. По большому счету, все так же, как и в обходе любой коллекции, используя цикл или рекурсию. Только в случае деревьев способов обхода больше, чем просто слева направо и справа налево.</p>
1
<p>Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется<strong>обходом дерева</strong>. Подразумевается, что в процессе обхода каждый узел будет затронут только один раз. По большому счету, все так же, как и в обходе любой коллекции, используя цикл или рекурсию. Только в случае деревьев способов обхода больше, чем просто слева направо и справа налево.</p>
2
<p>В данном курсе используется один порядок обхода -<strong>обход в глубину</strong>, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать на википедии либо в рекомендуемых Хекслетом книгах.</p>
2
<p>В данном курсе используется один порядок обхода -<strong>обход в глубину</strong>, так как он естественным образом получается при рекурсивном обходе. Об остальных способах можно прочитать на википедии либо в рекомендуемых Хекслетом книгах.</p>
3
<h2>Обход в глубину (Depth-first search)</h2>
3
<h2>Обход в глубину (Depth-first search)</h2>
4
<p>Это один из методов обхода дерева. Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.</p>
4
<p>Это один из методов обхода дерева. Стратегия этого поиска состоит в том, чтобы идти вглубь одного поддерева настолько, насколько это возможно. Этот алгоритм естественным образом ложится на рекурсивное решение и получается сам собой.</p>
5
<p>Рассмотрим данный алгоритм на примере следующего дерева:</p>
5
<p>Рассмотрим данный алгоритм на примере следующего дерева:</p>
6
<p>Каждая нелистовая вершина обозначена звездочкой. Обход начинается с корневого узла.</p>
6
<p>Каждая нелистовая вершина обозначена звездочкой. Обход начинается с корневого узла.</p>
7
<ol><li>Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребенка независимо;</li>
7
<ol><li>Проверяем, есть ли у вершины A дети. Если есть, то запускаем обход рекурсивно для каждого ребенка независимо;</li>
8
<li>Внутри первого рекурсивного вызова оказывается следующее поддерево:</li>
8
<li>Внутри первого рекурсивного вызова оказывается следующее поддерево:</li>
9
</ol><p>Повторяем логику первого шага. Проваливаемся на уровень ниже.</p>
9
</ol><p>Повторяем логику первого шага. Проваливаемся на уровень ниже.</p>
10
<ol><li>Внутри оказывается листовой элемент E. Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх</li>
10
<ol><li>Внутри оказывается листовой элемент E. Функция убеждается, что у узла нет дочерних элементов, выполняет необходимую работу и возвращает результат наверх</li>
11
<li>Снова оказываемся в ситуации:</li>
11
<li>Снова оказываемся в ситуации:</li>
12
</ol><p>В этом месте, как мы помним, рекурсивный вызов запускался на каждом из детей. Так как первый ребенок уже был посещен, второй рекурсивный вызов заходит в узел F и выполняет там свою работу. После этого происходит возврат выше, и все повторяется до тех пор, пока не дойдет до корня.</p>
12
</ol><p>В этом месте, как мы помним, рекурсивный вызов запускался на каждом из детей. Так как первый ребенок уже был посещен, второй рекурсивный вызов заходит в узел F и выполняет там свою работу. После этого происходит возврат выше, и все повторяется до тех пор, пока не дойдет до корня.</p>
13
<p>Печать на экран в примере выше - это лишь демонстрация. В реальности же нас интересует либо изменение дерева, либо агрегация данных по нему. Агрегацию данных рассмотрим позже, а сейчас разберем изменение.</p>
13
<p>Печать на экран в примере выше - это лишь демонстрация. В реальности же нас интересует либо изменение дерева, либо агрегация данных по нему. Агрегацию данных рассмотрим позже, а сейчас разберем изменение.</p>
14
<p>Допустим, мы хотим реализовать функцию, которая меняет владельца для всего дерева, то есть всех директорий и файлов. Для этого нам придется соединить две вещи: рекурсию, разобранную выше, и код обновления узлов, который изучался в прошлом уроке.</p>
14
<p>Допустим, мы хотим реализовать функцию, которая меняет владельца для всего дерева, то есть всех директорий и файлов. Для этого нам придется соединить две вещи: рекурсию, разобранную выше, и код обновления узлов, который изучался в прошлом уроке.</p>
15
<p>Ключевое отличие от первого примера - вместо печати на экран, формируются новые узлы и возвращаются наружу. В конце концов из них собирается новое дерево.</p>
15
<p>Ключевое отличие от первого примера - вместо печати на экран, формируются новые узлы и возвращаются наружу. В конце концов из них собирается новое дерево.</p>
16
<p>Все, что будет дальше делаться по ходу курса, неизменно<strong>базируется на этом алгоритме</strong>. Попробуйте открыть редактор на своем компьютере и самостоятельно реализовать эту функцию без подглядывания. Так вы убедитесь в том, что поняли происходящее.</p>
16
<p>Все, что будет дальше делаться по ходу курса, неизменно<strong>базируется на этом алгоритме</strong>. Попробуйте открыть редактор на своем компьютере и самостоятельно реализовать эту функцию без подглядывания. Так вы убедитесь в том, что поняли происходящее.</p>