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