Деревья. Корень, листья, высота и перебор вариантов

Читать укоренённое дерево, находить корень, листья и поддерево; различать глубину узла и высоту дерева в рёбрах; построить своё дерево вариантов, перечислить допустимые листья и объяснить исключённые ветви.

Рассматриваем непустые укоренённые деревья: все узлы достижимы от указанного корня, у корня нет родителя, у каждого другого узла ровно один родитель; циклов нет. Стрелки идут от родителя к ребёнку. Уровень/глубина корня 0; высота равна наибольшему числу рёбер от корня до листа. В дереве из одного корня высота 0, и корень одновременно лист. Рисунок не измеряют линейкой. Буквы/коды в данных различают узлы; одинаковые надписи у разных узлов вообще возможны и сами по себе дерево не нарушают.

Для работы достаточно бумаги, ручки и памятки. Сохраняй первую попытку; исправления отмечай другим знаком.

Безопасное начало

Сухие руки, без напитков у техники. Провода и разъёмы не трогай, о неисправности сообщи учителю. Работай по правилам кабинета. Две полные минуты в середине урока — без экрана и заданий. Внешний ИИ, личные аккаунты и личные данные не требуются.

Что уже нужно знать

Вершины, дуги и пути из уроков 009–010; последовательный просмотр всех выходов. Весовая оптимизация, двоичный поиск и программирование не требуются.

S0. Путь проходит два ребра с весами 4 и 7. Назови число рёбер и сумму весов. Что нужно считать, если речь идёт о количестве переходов, а не о стоимости пути?

Устная проба без отметки.

Корень, листья и путь до потомка

Дерево представляет иерархию или последовательный выбор. Здесь у одного указанного корня нет родителя, у каждого другого узла ровно один родитель; от корня достижимы все узлы, циклов нет. Стрелки направлены от родителя к ребёнку. Лист — узел без детей; он не обязательно расположен на самом глубоком уровне. Глубина узла — число рёбер от корня до него, у корня 0. Высота всего дерева — максимальная глубина листа; считать надо рёбра, а не узлы пути и не сумму их весов. В дереве из одного корня высота 0, корень одновременно лист. Поддерево с корнем v содержит сам v и всех его потомков; его высота отсчитывается от v. Для перебора каждая стадия выбора даёт следующий уровень. Один путь от начала до полного листа — один полный вариант. Сначала охвати все исходные выборы, затем отметь точные запреты. Число листьев-кандидатов и число допустимых листьев могут различаться. У разных узлов могут быть одинаковые надписи; один и тот же некорневой узел не может иметь двух родителей в нашем дереве.

Все деревья учебные, непустые, корень указан. Длины линий на рисунке не являются данными. Порядок размещения ветвей можно менять при сохранении связей и этапов выбора; число вариантов от этого не меняется.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Личная проба

C1. Дерево имеет корень R и только связи родитель→ребёнок: R→A, R→B, A→C, A→D, B→E, E→F. У других узлов детей нет. Назови корень, все листья и число рёбер. Высота считается в рёбрах, глубина корня 0: найди высоту и один самый длинный путь от корня до листа.

Точные связи C1. Высота определяется числом рёбер, а не длиной линий.

Две минуты лично прочитать дерево, затем две на сверку самого длинного пути. Памятка разрешена.

Сменить корень отсчёта для поддерева

Разобранная модель: корень U, только U→V, U→W, V→X, V→Y. Листья W,X,Y. Высота всего дерева 2 по U→V→X или U→V→Y, глубина W равна 1. Поддерево V содержит V,X,Y и имеет высоту 1 от V. Поэтому глубина одного узла, высота всего дерева и высота поддерева могут различаться.

A1. В другом дереве корень T; только связи T→M, T→N, M→P, M→Q, Q→S, других детей нет. Высота и глубина считаются в рёбрах, у корня глубина 0. Поддерево с корнем M включает сам M и всех его потомков. Перечисли узлы этого поддерева, найди его высоту от M. Затем назови глубину N от T и высоту всего дерева от T.

Сначала своя запись и основание, затем сверка.

Полная пауза

Две минуты без проекции, чтения, вычислений и обсуждения. Отведи взгляд и смени позу.

Каждый полный путь — отдельный вариант

Разобранный перебор на других символах: первая буква H/J, затем цифра 2/3, запрещён только J2. Корень O; после него H/J, затем полные листья H2,H3,J2,J3. Четыре кандидата, три допустимых H2,H3,J3. Запрещённый J2 отмечают отдельно, J3 остаётся. Высота полного дерева 2 ребра, хотя видны три уровня.

A2. Код состоит ровно из двух символов: сначала A или B, затем 0 или 1. Оба выбора делаются именно в таком порядке; других символов нет. Единственное запрещённое сочетание — B1. Дерево начинается в корне O, затем ветви A/B, затем лист каждого полного кода. Перечисли все четыре кандидата, отметь запрещённый и запиши все допустимые коды. Объясни, почему ветвь B не надо удалять целиком.

Три минуты собственный полный список, две на проверку исключения и сохранённой ветви.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Построить своё дерево и проверить листья

Сначала обозначь начало выбора, затем все варианты первого символа. От каждой первой ветви проведи все разрешённые вторые выборы и подпиши каждый лист полным кодом. Отдельно отметь точные запрещённые сочетания. Перечисли допустимые листья, сверяй список по каждой первой букве. Для высоты пройди от начала до полного листа и посчитай рёбра. Не объединяй разные исходы в один узел с несколькими родителями.

B1. Построй своё полное дерево двухсимвольных учебных кодов. Первый символ K или L, второй — 1,2 или 3; иных вариантов нет. Корень O означает начало выбора, следующий уровень — первая буква, последний — полный код. Нарисуй все ветви и шесть листьев-кандидатов. Единственный запрет — L2: пометь этот лист как недопустимый, остальные сохраняй. Запиши список допустимых кодов и их количество. Высота считается в рёбрах от O: назови её и объясни, почему нельзя вместо шести полных листьев сделать три общих узла 1,2,3 с двумя родителями каждый. Сначала своя схема/запись, потом исправления другим знаком.

Шесть минут: 4 собственная схема и список, 1 проверка высоты/запрета, 1 сверка. Сначала свои следы решения.

Проверка вымышленного ответа ИИ

AI1. Вымышленный ИИ говорит о B1: «Высота равна 3, ведь видны три уровня с корнем. Чтобы сократить рисунок, сделаем один общий узел 1 ребёнком и K, и L». Найди и исправь обе ошибки по принятому определению дерева и высоты.

Это заранее составленный учебный пример. Самостоятельно проверь конкретный шаг; обращение к сервису не требуется.

Помощь и резерв

• Считает узлы вместо рёбер. Поставь у корня 0 и увеличивай число после каждого перехода.
• Листом считает только самый нижний узел. Проверь отсутствие детей у каждого узла.
• Забывает корень поддерева. Обведи выбранный корень вместе со всеми потомками.
• Удаляет всю ветвь по одному запрету. Сверь каждый полный код с точным условием.

D1. Резерв. К каждому допустимому коду B1 добавляют третий символ x или y. Запрет L2 сохраняется независимо от третьего символа. Сколько допустимых трёхсимвольных кодов получится? Какова высота полного дерева от начала выбора в рёбрах? Покажи два продолжения одного разрешённого кода и объясни счёт.

D1 — необязательный резерв на 3–4 минуты после основных попыток. При нехватке времени перенести. H1 и весь тест автоматически вместе не назначаются.

Индивидуальный итог

Четыре полные минуты лично. Условия заранее на бумаге. Памятка и разобранные модели разрешены; ключи и веб-разбор закрыты. Учитель не даёт учебных подсказок. Сбор после четырёх минут.

E1. В дереве корень R имеет только двух детей A и B, у них детей нет. Высота считается в рёбрах, корень имеет глубину 0. Назови высоту дерева и оба листа.

E2. Поддерево с корнем P включает сам P и всех его потомков. У P дети Q и R, у R ребёнок S; других потомков нет. Перечисли все узлы этого поддерева.

E3. Двухсимвольный код: сначала X или Y, затем 1 или 2. Единственный запрет — Y2. Запиши все допустимые коды и объясни одно исключение.

Разбор после своей попытки

Показать ответ после выполнения

После исправления выбери один новый пример из самопроверки.

Файлы для собственной практики

• Точное дерево C1

Исходное дерево C1 повторяет полный текст связей. Все обязательные задания выполняются на бумаге; практикум не требует реальных паролей или личных данных.

Материалы и самопроверка

Презентация, самостоятельный план учителя, рабочий лист, выходной билет и бумажная самопроверка открываются отдельными карточками. DOCX можно смотреть на сайте и скачать. PDF для печати:

• Рабочий лист
• Выходной билет — два на А4
• Самопроверка на бумаге

Самопроверка на сайте: шесть вопросов с пояснениями, отдельно 6–8 минут. Бумажная версия с письменными основаниями и разбором — 8–12 минут. Все шесть новых письменных случаев — ещё 8–10 минут; выбирай прежде всего случай к своей ошибке. Эти модули не прибавляют к основным 45 минутам и не задаются целиком вместе с H1 автоматически. Пояснения и новые случаи для бумажного разбора есть в плане учителя.

Домашний перенос

H1. Дома 5–7 минут на бумаге. Двухсимвольный код: сначала P или Q, затем 0,1 или 2. Запрещены только P1 и Q0. Построй полное дерево с корнем O и отдельными листьями полных кодов, пометь запрещённые. Запиши допустимые коды и количество. Высота считается в рёбрах, у O глубина 0: назови высоту полного дерева.

Полное условие и памятка есть на листе. Решение запиши в тетради. Достаточно 5–7 минут с сохранённой опорой.

Источники

ФРП информатики 7–9 классов, базовый уровень: содержание 9 класса, раздел 2 «Теоретические основы информатики», моделирование, печатные с. 40–41: дерево, корень, узел, лист, ребро, высота, поддерево и перебор вариантов с помощью дерева. Здесь час 011 авторского КТП 2026/2027. Соглашение о высоте в рёбрах и корне на уровне 0 указано прямо. Учебник школы не указан; номера параграфов не назначены.

• Федеральная рабочая программа информатики 7–9 классов, базовый уровень
• Информационно-методическое письмо по информатике на 2026/2027 год
• NIST DADS — дерево и иерархия узлов
• NIST DADS — корень
• NIST DADS — лист
• NIST DADS — высота дерева
• NIST DADS — глубина узла
• NIST DADS — поддерево