TwiddleLab / Код / Структуры данных, которые видно
Деревья: папки внутри папок
Что ты узнаешь
- У дерева один корень; у каждого другого узла один родитель и сколько угодно детей. Узлы без детей это листья.
- Многое устроено как дерево: папки, семья, турнир, меню страницы, викторина из вопросов «да или нет».
- Чтобы обойти дерево, держи стек: снимай узел, клади его детей. С очередью вместо стека идёшь уровень за уровнем.
- Итоги вроде размеров папок складываются от листьев к корню.
Как идёт урок
Телефон пишет «Память почти заполнена».
Размер показывают только файлы. Какая папка в верхнем ряду съедает место? Нажми на свою ставку.
Сложи всё, как это делает телефон.
Размер папки это сумма того, что внутри. Нажимай на папки, как только всё внутри известно.
Папка не может знать свой размер, пока у каждого ребёнка нет размера. Поэтому размеры текут вверх: сначала файлы, потом папки с ними, а корень последним.
Как программа обходит каждую папку?
Она держит стек, твои тарелки из урока 1. Жми «Шаг» и нажимай на то, что снимется следующим.
Такая форма это дерево.
Дерево начинается с одного корня. У каждого другого узла ровно один родитель, и у него могут быть дети. Узлы без детей это листья.
Посетить каждый узел это обход. Со стеком он идёт сначала вглубь; с очередью уровень за уровнем.
В Python дерево может быть словарём от каждой папки к списку её детей: {"Phone": ["Photos", "Music"], "Photos": ["Trip"]}.
Построй своё дерево папок.
Перетащи каждую карточку в папку. Положи часть внутрь новых папок, чтобы сделать дерево глубже.
Стек или очередь?
Два обходчика прошли это дерево. Один держал стек, другой очередь. Подпиши каждый порядок, потом «Проверить».
Стек отдаёт детей, которых только что положили, поэтому обход продолжает спускаться. Очередь отдаёт самый давно ждущий узел, поэтому все узлы одного уровня идут раньше следующего.
Найди обжору.
Найди самый большой файл на этом телефоне. Открой как можно меньше папок.
Дерево вопросов.
ИИ тоже использует деревья: каждый узел задаёт вопрос, каждый лист это ответ. Отправь каждую зверушку вниз до её листа.
Вернёмся к твоему дереву.
Нажми на его корень и смотри, как размеры складываются от листьев.
Предыдущий урок: Множества: оно там есть? · Следующий урок: Двоичные деревья поиска · Часть курса: Структуры данных, которые видно
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
