1. Где используются структуры типа «дерево» в информатике и в других областях?
Деревья широко используются в информатике для организации данных (например, файловые системы, базы данных, структуры JSON/XML), в алгоритмах (поиск, сортировка) и в других областях, таких как биология (филогенетические деревья), лингвистика (синтаксические деревья) и управление проектами (иерархические структуры).
2. Объясните рекурсивное определение дерева.
Рекурсивное определение дерева звучит так: дерево состоит из корневого узла и поддеревьев, каждое из которых также является деревом.
3. Можно ли считать, что линейный список — это частный случай дерева?
Да, линейный список можно считать частным случаем дерева, где каждый узел имеет максимум одного потомка.
4. Какими свойствами обладает дерево поиска?
Дерево поиска обладает следующими свойствами: левое поддерево каждого узла содержит значения меньше узла, правое — больше, а поддеревья также являются деревьями поиска.
5. Подумайте, как можно построить дерево поиска из массива данных.
Для построения дерева поиска из массива сначала выбирают корневой узел, затем последовательно добавляют элементы, сравнивая их с текущими узлами для размещения слева или справа.
6. Какие преимущества имеет поиск с помощью дерева?
Дерево позволяет быстро искать, добавлять и удалять элементы, обеспечивая логарифмическую сложность операций.
7. Какие способы обхода дерева вы знаете? Придумайте какие- нибудь другие способы обхода.
Мне известны следующие способы обхода: прямой, обратный, симметричный и уровень за уровнем. Можно придумать обход на основе приоритета узлов, например, по их значениям.
8. Как строится дерево для вычисления арифметического выражения?
Дерево для арифметического выражения строится с корнем, представляющим оператор, а его дочерними узлами являются операнды (либо числа, либо другие операторы).
9. Как можно представить дерево в программе на Python?
В Python дерево представляют с помощью классов, где узел содержит данные, ссылки на левого и правого потомков.
10. Как указать, что узел дерева не имеет левого (правого) сына?
Чтобы указать отсутствие сына, используют значение None для ссылки на соответствующего потомка.
11. Как вы думаете, почему рекурсивные алгоритмы работы с деревьями получаются проще, чем нерекурсивные?
Рекурсивные алгоритмы проще из-за естественного соответствия рекурсии и иерархической структуры дерева.
12. Как хранить двоичное дерево в массиве? Можно ли использовать такой приём для хранения деревьев, в которых узлы могут иметь больше двух сыновей?
Двоичное дерево хранят в массиве, где узел с индексом i имеет потомков на индексах 2i+1 (левый) и 2i+2 (правый). Этот метод не подходит для деревьев с произвольным количеством сыновей, так как узлы могут занимать больше памяти.