бинарныеДеревья

1. Бинарные деревья

2.

• Бинарное дерево — это иерархическая структура данных, в
которой каждый узел имеет значение (оно же является в данном
случае и ключом) и ссылки на левого и правого потомка.

3.

4.

• Узел, находящийся на самом верхнем уровне (не являющийся
чьим либо потомком) называется корнем. Узлы, не имеющие
потомков (оба потомка которых равны NULL) называются
листьями.
корень
лист

5. Бинарное дерево поиска

• Бинарное дерево поиска — это бинарное дерево, обладающее
дополнительными свойствами: значение левого потомка меньше
значения родителя, а значение правого потомка больше значения
родителя для каждого узла дерева

6. Сбалансированное бинарное дерево поиска

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

7. Экстремально несбалансированное бинарное дерево поиска

8. Рекурсия

• Рекурсия в программировании – это вызов функцией самой себя с
другими аргументами. В принципе, рекурсивная функция может
вызывать сама себя и с теми же самыми аргументами, но в этом
случае будет бесконечный цикл рекурсии, который закончится
переполнением стека. Внутри любой рекурсивной функции должен
быть базовый случай, при котором происходит выход из функции, а
также вызов или вызовы самой себя с другими аргументами.
Аргументы не просто должны быть другими, а должны приближать
вызов функции к базовому случаю. Например, вызов внутри
рекурсивной функции расчета факториала должен идти с меньшим по
значению аргументом, а вызовы внутри рекурсивной функции обхода
дерева должны идти с узлами, находящимися дальше от корня, ближе
к листьям. Рекурсия может быть не только прямой (вызов
непосредственно себя), но и косвенной. Например А вызывает Б, а Б
вызывает А

9. Способы обхода

Есть 3 способа обхода:
• 1. Обход в прямом порядке — сверху вниз: A, B,
C — префиксная форма.
• 2. Обход слева направо (симметричный
порядок): B, A, C — инфиксная форма.
• 3. Обход снизу вверх (обратный порядок): B, C,
A — постфиксная форма.

10. Прямой обход

• При прямом обходе мы
посещаем родительские
узлы до посещения
узлов-потомков. В случае
с нашим деревом мы
будем обходить узлы в
таком порядке: 1, 2, 4, 5,
3.

11. Обратный обход

• вы сначала посещаете
узлы-потомки, а затем —
их родительские узлы. В
нашем случае порядок
посещения узлов при
обратном обходе будет
таким: 4, 5, 2, 3, 1.

12. Центрированный обход

• Посещение всех узлов
слева направо.
Центрированный обход
нашего дерева — это
посещение узлов 4, 2, 5,
1, 3.

13. Ссылки

• Алгоритм на python с ООП и рекурсией
http://py-algorithm.blogspot.com/2011/07/blog-post_30.html
• Еще один алгоритм на Python
https://pythonist.ru/obhod-dvoichnogo-dereva-na-python/
• Английский ресурс
https://www.section.io/engineering-education/binary-tree-datastructure-python/

14. Задание 1

• Реализовать структуру бинарного дерева
• Реализовать обход бинарного дерева на выбор.

15. Задание 2