Бинарное дерево: обходы, вершины, рёбра и проверка свойств
Цели и задачи
- Цель урока по SMART: к концу урока научиться распознавать структуру бинарного дерева, выполнять прямой и симметричный обход, подсчитывать вершины и рёбра, определять листья и проверять граф по заданным свойствам с успешным выполнением не менее 4 из 5 аналогичных заданий рабочего листа.
- Сформировать представление о бинарном дереве как о связном графе без циклов, в котором у каждой вершины не более двух детей.
- Научиться выполнять прямой и симметричный обход дерева по заданному порядку посещения вершин.
- Научиться определять число вершин, листьев и рёбер, а также высоту полного бинарного дерева.
- Развивать алгоритмическое мышление и уверенность при решении заданий, близких к формату ОГЭ.
Планируемые результаты
Личностные
- Осознают, что последовательный алгоритм проверки графа снижает количество случайных ошибок при решении экзаменационных заданий.
- Проявляют ответственное отношение к точности записи последовательностей вершин, рёбер и результатов подсчёта.
- Оценивают собственный уровень понимания темы и формулируют способ преодоления затруднения.
- Понимают практическую ценность деревьев для представления иерархий, файловых систем и алгоритмов поиска.
Метапредметные
- Выделяют существенные признаки бинарного дерева и отделяют их от второстепенных данных условия.
- Строят алгоритм решения: определить корень, установить связи, проверить связность и отсутствие циклов, затем выполнить требуемый подсчёт.
- Читают таблицы смежности и преобразуют табличное представление в список соседей или граф.
- Работают в паре, аргументируют ответ и проверяют решение по критериям.
- Используют самопроверку и исправляют ошибки после сравнения с эталоном.
Предметные
- Знать понятия «вершина», «ребро», «корень», «родитель», «потомок», «лист», «поддерево», «высота дерева».
- Уметь выполнять прямой обход по схеме «корень — левое поддерево — правое поддерево».
- Уметь выполнять симметричный обход по схеме «левое поддерево — корень — правое поддерево».
- Уметь подсчитывать вершины, листья и рёбра дерева, включая полное бинарное дерево.
- Уметь проверять, является ли заданный граф деревом и бинарным деревом с указанным корнем.
Универсальные учебные действия (УУД)
Личностные УУД
- Осознают личную ответственность за результат пошаговой проверки решения.
- Связывают изучаемый материал с подготовкой к ОГЭ и будущей деятельностью в сфере технологий.
- Формируют установку на проверку гипотезы по нескольким признакам, а не по внешнему сходству схемы.
- Принимают ошибку как источник уточнения алгоритма.
Регулятивные УУД
- Формулируют цель решения конкретного задания и выбирают подходящий алгоритм.
- Планируют последовательность действий при восстановлении дерева по списку связей.
- Осуществляют пошаговый самоконтроль по чек-листу: вершины, рёбра, связность, циклы, дети.
- Сверяют результат с эталоном и корректируют неверный порядок обхода или подсчёт.
- Оценивают выполнение рабочего листа по заданным критериям.
Познавательные УУД
- Сравнивают прямой и симметричный обходы и выделяют различие в положении корня.
- Моделируют дерево в виде схемы, списка связей и таблицы смежности.
- Устанавливают связь между числом вершин и рёбер в дереве.
- Анализируют степень вершины графа и определяют её соседей по строке таблицы.
- Применяют формулу числа вершин полного бинарного дерева для заданного количества уровней.
Коммуникативные УУД
- Объясняют партнёру порядок обхода, используя точные термины.
- Распределяют роли при работе с карточкой: читатель условия, построитель схемы, проверяющий.
- Задают уточняющие вопросы о корне, направлении связи и количестве детей.
- Аргументируют вывод о том, является ли граф деревом или бинарным деревом.
- Согласуют общий ответ и корректно обсуждают найденную ошибку.
Подготовка учителя к уроку
- Подготовить рабочий лист с десятью заданиями о бинарном дереве и графах — по одному экземпляру на каждого ученика.
- Подготовить три комплекта карточек для дифференциации: базовый, стандартный и повышенный; по одному комплекту на пару.
- Вывести на доску или на экран определения «вершина», «ребро», «корень», «лист», «потомок», «бинарное дерево».
- Заранее записать на доске схемы обходов: прямой — корень, левое поддерево, правое поддерево; симметричный — левое поддерево, корень, правое поддерево.
- Подготовить карточку-чек-лист проверки графа: число вершин, число рёбер, связность, отсутствие циклов, число детей каждой вершины.
- Распечатать мини-таблицу самооценки и билет на выход — по одному листку на ученика.
- Подготовить маркеры, стикеры, магнитные карточки с буквами A, B, C, D, E, F и листы формата А4 для построения схем.
- Подготовить проектор или интерактивную доску для показа деревьев, таблиц смежности и эталонов решений.
- Проверить, что в задании с таблицей смежности для графа из пяти вершин видна полная таблица; если исходная таблица обрезана, использовать полную таблицу, выданную на рабочем листе.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в учебную деятельность и показать практическую связь темы с экзаменационными заданиями и информатикой.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране схему папок компьютера, представленную как дерево: "Здравствуйте, ребята. Сегодня мы будем изучать структуру, которая встречается в файловых системах, алгоритмах поиска и заданиях ОГЭ. Посмотрите на схему: одна вершина соединена с другими, а от некоторых вершин связи продолжаются дальше. Как вы думаете, почему такую структуру удобно называть деревом?" | Рассматривают схему и предполагают: "Есть вершина сверху и ветви вниз", "структура разбивается на уровни". |
2 мин | Учитель сообщает тему и ожидаемый результат: "Сегодня мы научимся читать бинарное дерево несколькими способами. К концу урока вы сможете решить задания рабочего листа на прямой и симметричный обход, листья, высоту, рёбра и проверку графа. Это не угадывание: мы составим точный алгоритм, который можно применять на ОГЭ." | Записывают тему, формулируют личную цель: "научиться выполнять обход", "не путать число вершин и рёбер", "проверять, является ли граф бинарным деревом". |
Завершение этапа: учитель подводит итог: "Мы увидели, что дерево — это не рисунок ради рисунка, а способ хранить связи. Теперь вспомним, из каких элементов состоит такая структура и какие признаки нужно проверять."
Этап 2. Актуализация знаний и выявление затруднения (6 мин)
Цель этапа: актуализировать понятия графа и выявить, какие действия необходимы для анализа дерева.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель прикрепляет на доску карточки A, B, C, D, E и соединяет их связями AB, AC, BD, BE, CF на отдельной схеме: "Назовите элементы, которые вы видите. Что обозначают буквы? Что обозначают линии? Если A — корень, как назвать B и C?" Учитель уточняет: "Может ли у вершины бинарного дерева быть три непосредственных ребёнка?" | Отвечают: "Буквы — вершины, линии — рёбра", "B и C — дети или потомки A", "у вершины бинарного дерева не более двух детей". |
3 мин | Учитель раздаёт парам мини-карточку с деревом A: слева B, справа C: "Попробуйте без подсказки назвать вершины в порядке прямого обхода. Затем объясните, почему вы начали именно с этой вершины. Какие данные нужно проверить, если дерево дано не рисунком, а списком связей?" | В парах записывают A, B, C; объясняют: "Сначала корень, затем левое поддерево, затем правое". Называют признаки: количество вершин и рёбер, связность, отсутствие циклов, число детей. |
Завершение этапа: учитель подводит итог: "Мы уже можем прочитать простое дерево, но пока важно договориться о едином алгоритме. Сейчас сформулируем проблему урока: как по разным представлениям — рисунку, списку связей и таблице — надёжно определить свойства бинарного дерева?"
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: сформулировать алгоритм анализа дерева и критерии успешного решения заданий рабочего листа.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает на экране два изображения: дерево и список связей A–B, A–C, B–D, B–E, C–F: "Перед нами одна и та же структура, представленная по-разному. Как проверить, что мы не потеряли вершину или связь? Составим план: сначала читаем условие и отмечаем корень; затем строим схему или список соседей; после этого считаем вершины и рёбра; проверяем связность, циклы и число детей." | Формулируют план действий и записывают его кратко. Предлагают дополнение: "Для обхода нужно отдельно определить, левый это ребёнок или правый". |
2 мин | Учитель возвращается к рабочему листу: "В заданиях 1 и 4 нужно выполнить обход, в заданиях 2, 3, 5 и 7 — подсчёт, в заданиях 6 и 8 — чтение таблицы, а в заданиях 9 и 10 — проверка свойств графа. Сегодня мы разберём образцы, а затем вы примените алгоритм самостоятельно." | Распределяют задания по типам и отмечают в листе, какие понятия понадобятся для каждого типа. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "Цель определена: научиться переходить от условия к схеме и от схемы к доказанному ответу. Начнём с самого важного инструмента — порядка обхода вершин."
Этап 4. Открытие нового знания (10 мин)
Цель этапа: вывести правила прямого и симметричного обхода, связать их с подсчётом вершин, листьев, рёбер и высоты.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает дерево из задания №4: корень 8, слева 3, справа 10; у 3 дети 1 и 6; у 10 правый ребёнок 14. "Сначала выполним прямой обход. Правило записано на доске: корень — левое поддерево — правое поддерево. Мы посещаем 8, затем полностью рассматриваем левую часть с корнем 3, затем правую часть с корнем 10. Какая последовательность получится?" | По схеме записывают прямой обход: 8, 3, 1, 6, 10, 14. Проговаривают: "Сначала корень 8, затем левое поддерево 3, 1, 6, затем правое поддерево 10, 14". |
3 мин | Учитель закрывает предыдущую запись и показывает второе правило: "Теперь меняем только место корня: левое поддерево — корень — правое поддерево. Для вершины 3 сначала идёт 1, потом 3, потом 6. Для корня 8 после левой части идёт 8, затем правая часть. Запишите последовательность симметричного обхода и проверьте её по схеме." | Записывают симметричный обход: 1, 3, 6, 8, 10, 14. Сверяют порядок и объясняют, почему 8 стоит между левым и правым поддеревьями. |
2 мин | Учитель показывает дерево из задания №3: A имеет детей B и C, а C имеет детей D и E: "Лист — это вершина без детей. Не считайте все конечные линии на глаз, а проверьте каждую вершину. Какие вершины не имеют детей?" Затем показывает задание №2 с R, L, M, N и просит посчитать все вершины. | Определяют листья B, D, E; записывают, что листьев 3. В задании №2 перечисляют R, L, M, N и получают 4 вершины. |
2 мин | Учитель разбирает задание №5: "В полном бинарном дереве каждый уровень после корня заполнен. При трёх уровнях количество вершин по уровням равно 1, 2 и 4. Складываем: $1+2+4=7$. Важно не перепутать количество уровней и количество рёбер от корня до самого дальнего листа." | Записывают: при трёх уровнях полное бинарное дерево содержит 7 вершин. Формулируют вывод: "На каждом следующем уровне число вершин удваивается". |
Запись в тетрадях
- Бинарное дерево — связный граф без циклов, в котором у каждой вершины не более двух детей.
- Прямой обход: корень — левое поддерево — правое поддерево.
- Симметричный обход: левое поддерево — корень — правое поддерево.
- Лист — вершина без детей. В дереве из $n$ вершин число рёбер равно $n-1$.
- Для полного бинарного дерева с тремя уровнями число вершин: $1+2+4=7$.
Завершение этапа: учитель подводит итог: "Мы получили правила, которые позволяют решать задания 1–5 рабочего листа. Теперь применим их к конкретным условиям и научимся переводить список связей или таблицу смежности в понятную схему."
Этап 5. Первичное закрепление по рабочему листу (8 мин)
Цель этапа: отработать алгоритм на заданиях 6, 7, 9 и 10 с проговариванием каждого шага.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель обращается к заданию №6: "Работаем с таблицей смежности. Строки и столбцы идут в порядке A, B, C, D. Чтобы найти соседей C, смотрим строку C и отмечаем единицы: под A стоит 1, под B стоит 1, под C — 0, под D — 0. Что это означает?" | Находят соседей C: A и B; называют степень вершины C равной 2. Записывают: "соседи C — A, B; степень — 2". |
2 мин | Учитель разбирает задание №7: "Перечислены связи A–B, A–C, B–D, B–E, C–F. Сначала не смешиваем понятия. Каждая запись — одно ребро. Сколько записей? Сколько разных вершин встречается? Проверьте формулу дерева: рёбер на одно меньше, чем вершин." | Считают 5 рёбер и 6 вершин, перечисляют A, B, C, D, E, F и формулируют: "5 = 6 - 1". |
3 мин | Учитель показывает задание №10: "Проверяем не по внешнему виду, а по трём условиям. В графе вершины A, B, C, D, E, F и рёбра AB, AC, BD, BE, CF. Постройте схему с A сверху. Сколько детей у A, B и C? Есть ли связь со всеми вершинами? Есть ли цикл?" | Строят схему: A имеет детей B и C; B — D и E; C — F. Считают 6 вершин и 5 рёбер, отмечают связность и отсутствие циклов, отвечают: "Да, это бинарное дерево с корнем A, потому что у каждой вершины не более двух детей". |
Эталон решения
Задание №10: 1) В графе 6 вершин: A, B, C, D, E, F. 2) Записано 5 рёбер: AB, AC, BD, BE, CF. 3) Из A можно попасть в B и C, из B — в D и E, из C — в F, поэтому граф связный. 4) Циклов нет, так как ни одна вершина не возвращает нас к уже пройденной вершине другим путём. 5) При корне A число детей: у A — 2, у B — 2, у C — 1, у D, E и F — 0. Следовательно, граф является бинарным деревом.
Завершение этапа: учитель подводит итог: "Мы проверили граф по строгому алгоритму: вершины, рёбра, связность, отсутствие циклов и число детей. Теперь каждый выполнит часть рабочего листа самостоятельно, а затем сверит результат с эталоном."
Этап 6. Самостоятельная работа с самопроверкой (10 мин)
Цель этапа: диагностировать индивидуальное владение алгоритмами обхода и проверки свойств бинарного дерева.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель объясняет инструкцию: "Самостоятельно выполните задания №1, №3, №4, №5 и №9 рабочего листа. Сначала сделайте черновую схему или выпишите вершины, затем запишите ответ. Не подглядывайте в соседнюю тетрадь: нам важно увидеть именно ваш способ рассуждения." | Записывают номера выбранных заданий и готовят черновые схемы. |
6 мин | Учитель наблюдает, задаёт только направляющие вопросы: "Какое правило обхода указано в условии? У вершины есть дети или это лист? Сколько уровней названо в задаче? Какие три признака нужно проверить в задании о графе?" | Решают задания индивидуально: для №1 записывают A, B, C; для №3 — 3 листа; для №4 — 1, 3, 6, 8, 10, 14; для №5 — 7; для №9 делают вывод, что граф является деревом. |
3 мин | Учитель выводит на экран эталон и организует самопроверку: "Поставьте плюс рядом с верным ответом, точку — рядом с ответом, где была арифметическая или терминологическая ошибка. Исправление запишите рядом, не стирая исходный ответ. Если ошиблись, определите, на каком шаге алгоритма это произошло." | Сверяют решения, исправляют ошибки, отмечают тип затруднения: обход, подсчёт, чтение таблицы или проверка признаков. |
Завершение этапа: учитель подводит итог: "Самопроверка показала не только количество правильных ответов, но и место ошибки. Осталось связать все приёмы в одну систему и проверить, сможете ли вы объяснить решение другому человеку."
Этап 7. Рефлексия, обобщение и домашнее задание (4 мин)
Цель этапа: обобщить алгоритм решения, оценить достижение цели и дать домашнее задание в том же формате.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём «Одноминутка»: "За одну минуту запишите три фразы: правило прямого обхода, правило симметричного обхода и первый шаг проверки графа на бинарное дерево. Затем поднимите зелёную карточку, если можете решить аналогичное задание самостоятельно, жёлтую — если нужен пример, красную — если правило пока неясно." | Записывают три фразы и показывают карточки. Формулируют ответы: "Сначала корень", "Сначала левое поддерево", "Сначала считаем вершины и рёбра и определяем связи". |
2 мин | Учитель объявляет домашнее задание и контрольные вопросы: "Выберите уровень по своей готовности. Перед выходом ответьте письменно: чем лист отличается от внутренней вершины? В каком обходе корень записывается между левым и правым поддеревьями? Почему в дереве из шести вершин пять рёбер?" | Записывают домашнее задание, отвечают на контрольные вопросы и сдают билет на выход. |
Критерии оценивания практической работы
- «5» — верно выполнены не менее 5 заданий рабочего листа, включая хотя бы одно задание на обход и одно на проверку графа; ответы обоснованы, порядок вершин и подсчёты записаны без ошибок.
- «4» — верно выполнены 4 задания, алгоритм в основном применён правильно, допущена не более чем одна вычислительная или техническая ошибка.
- «3» — верно выполнены 3 задания базового уровня, понятия вершины, ребра, листа и корня в целом различаются, но объяснение проверки графа неполное.
- «2» — выполнено менее 3 заданий или перепутаны основные правила обхода и признаки бинарного дерева; требуется повторная работа с алгоритмом.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какое правило помогает выполнить прямой и симметричный обход без перестановки вершин? | Проверка осознания различия двух алгоритмов обхода. |
На каком шаге вы проверяете, что граф является деревом? | Выявление понимания признаков дерева: связность, отсутствие циклов и соотношение вершин и рёбер. |
Какое задание рабочего листа оказалось самым сложным и почему? | Выявление субъективных точек затруднения и планирование коррекции. |
Можете ли вы объяснить однокласснику, почему в дереве из 6 вершин 5 рёбер? | Проверка осмысленности связи между числом вершин и рёбер. |
Завершающее слово учителя
"Сегодня мы научились рассматривать бинарное дерево не только как рисунок, но и как систему вершин и рёбер. Главное — не перепутать порядок обхода: в прямом обходе корень идёт первым, а в симметричном занимает место между левым и правым поддеревьями. При проверке графа всегда действуйте последовательно: посчитайте вершины и рёбра, проверьте связность, отсутствие циклов и число детей. На следующем уроке мы продолжим работу с алгоритмами обработки деревьев и решим больше заданий в формате ОГЭ."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Решить 4 задания: одно на прямой обход небольшого бинарного дерева, одно на симметричный обход, одно на подсчёт листьев и одно на определение числа вершин и рёбер по списку родитель–потомок. Для каждого задания записать краткое правило или шаг подсчёта. | Закрепляет основные понятия и алгоритмы урока; при проверке обратить внимание на порядок обхода, различение листьев и внутренних вершин, соответствие числа рёбер числу вершин. |
Средний (повышающий) | Решить 3 задания: построить дерево по таблице смежности на 4–5 вершинах, определить соседей выбранной вершины и степень; проверить, является ли полученный граф деревом; выполнить симметричный обход, если корень и левый и правый сыновья указаны. | Развивает перевод между таблицей, схемой и списком связей; при проверке смотреть на корректность чтения единиц и полноту обоснования. |
Продвинутый (дополнительный) | Составить собственное бинарное дерево из 7–9 вершин, записать список его рёбер, прямой и симметричный обходы, количество листьев и высоту. Затем предложить однокласснику проверить, является ли оно бинарным деревом с выбранным корнем. | Формирует умение создавать модель и проверять её по нескольким критериям; при проверке оценить отсутствие циклов, связность, число детей и согласованность всех представлений. |
Контрольные вопросы перед выходом из класса: «Что такое лист дерева?», «В каком порядке выполняется симметричный обход?», «Сколько рёбер имеет дерево с 8 вершинами?», «Какие признаки нужно проверить, чтобы назвать граф бинарным деревом с заданным корнем?»
