Деревья: двоичные, поиска, обходы, выражения

11 класс, углублённый уровень. Обзорный практикум к восьмой паре: шесть задач по содержанию темы.

Что нужно сделать: Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными, и её можно сдать ещё раз. Сколько закрыл, столько и наработал. Времени нужно около пятнадцати минут: дерево поиска, обход и дерево вызовов удобнее нарисовать на черновике.
Отметка и добор: Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Кнопка «Получить код» внизу страницы появляется, как только закрыто три вопроса: можно забрать код сразу, а можно дорешать оставшиеся и получить код получше — решать самому, до какой отметки добирать.
Ответ — число или буквы подряд: Число — без единиц и пробелов: 34. В задаче на обход — русские заглавные буквы вершин подряд: ГЛЕБМДА, а не Г, Л, Е…. На КЕГЭ ответ читает машина, и здесь так же.
Как сдать: В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
Не успел на уроке: Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.

Вопросы темы

наработано на—

Подсказка: деревья

Основные понятия

Дерево — связный граф без циклов: на n вершинах ровно n − 1 рёбер. Одна вершина — корень, у остальных ровно один родитель. Вершины без потомков — листья. Потомки вершины — всё поддерево под ней, не только ближайшие. Высота — число рёбер в самом длинном пути от корня до листа; уровней на один больше.

Двоичное дерево

у каждой вершины не больше двух потомков — левый и правый, и это не одно и то же;
на уровне k — не больше 2^k−1 вершин; на L уровнях — не больше 2^L − 1;
если у каждой вершины 0 или 2 потомка — листьев на один больше, чем вершин с двумя потомками.

Дерево поиска

Первое число — корень. Каждое следующее спускается от корня: меньше — влево, больше — вправо, пока не найдёт пустое место. Поиск идёт тем же путём: сравнений столько, сколько вершин на пути.

Обходы двоичного дерева

обход	порядок в каждом поддереве
прямой	корень, левое, правое
симметричный	левое, корень, правое
обратный	левое, правое, корень

У дерева поиска симметричный обход выдаёт числа по возрастанию.

Выражение в виде дерева

В листьях числа, в остальных вершинах знаки; знак применяется к левому и правому потомку — именно в этом порядке. Прямой обход даёт прямую польскую запись (− · 9 7 2), обратный — обратную (9 7 · 2 −). Обратную читают слева направо со стеком: число — в стек, знак снимает два верхних (первым снятое — правое) и кладёт результат.

Дерево вызовов

Рекурсивная функция F(n) = F(n − a) + F(n − b) порождает дерево: у вызова два потомка, вызов с базовым n — лист. Всего вызовов C(n) = 1 + C(n − a) + C(n − b), у листа C = 1; считать снизу вверх.

Материалы подготовлены с использованием технологий искусственного интеллекта.