Всякое дерево можно представить в виде бинарного дерева. При преобразовании сохраняется связь отца с самым левым (старшим) сыном. Они соединяются левой связью. Сыновья одного отца соединяются правыми
связями. Рис. 28 поясняет преобразование.
Рис. 28. Преобразование дерева общего вида к бинарному дереву
Отметим, что преобразование является взаимно однозначным.
Контрольные вопросы
1) Дайте определение дерева.
2) Дайте определение бинарного дерева.
3) Применительно к деревьям определите понятия: корень, лист, степень узла, отец, сын, предок, потомок, брат.
4) Определите прямой, обратный и концевой порядок обхода бинарного дерева.
5) Напишите функцию, вычисляющую высоту бинарного дерева.
6) Какие преимущества даёт прошивка бинарного дерева?
7) Какие способы представления деревьев общего вида вы знаете?
