Печать: Ctrl+P → ориентация альбомная, масштаб 100 % (не «вписать в лист»), поля нет, «печать фона» включить — иначе пропадут рамки таблиц. На листе две одинаковые карточки: разрезать по пунктиру посередине, получится две штуки формата A5. Эта серая рамка на бумагу не печатается.
11 класс

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

Обзорный практикум по содержанию ФГОС к восьмой паре 11 класса

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

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

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

  • у каждой вершины не больше двух потомков — левый и правый, и это не одно и то же;
  • на уровне k — не больше 2k−1 вершин; на L уровнях — не больше 2L − 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; считать снизу вверх.

Тренажёр и разбор темы: https://kibersvet.ru/11/derevya/
Материалы подготовлены с использованием технологий искусственного интеллекта.
11 класс

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

Обзорный практикум по содержанию ФГОС к восьмой паре 11 класса

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

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

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

  • у каждой вершины не больше двух потомков — левый и правый, и это не одно и то же;
  • на уровне k — не больше 2k−1 вершин; на L уровнях — не больше 2L − 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; считать снизу вверх.