Представление деревьев общего вида бинарными деревьями
Представление деревьев общего вида
Рассмотрим два варианта представления дерева общего вида. В первом варианте для хранения указателей на сыновей используется массив фиксированной длины:
const int MAXSON=10; // максимально возможное число сыновей
struct NODE {
<поля данных>;
int nSon; // действительное число сыновей узла
NODE *Sons[MAXSON];
};
В некоторых узлах память оказывается недоиспользованной, а также возможна ситуация, когда число сыновей узла окажется больше максимально допустимого.
От этого недостатка свободно представление, когда указатели на сыновей находятся в линейном списке. Такая списочная структура содержит два типа узлов – узлы дерева и узлы линейного списка сыновей.
struct SON { // узел списка сыновей
struct NODE *Son; // указатель на сына
struct SON *Next; // указатель на следующий узел
// списка сыновей
};
struct NODE { // узел дерева
<поля данных>;
SON *Sons; // указатель на начало списка сыновей
};
 |
На рис. 27 изображен пример такого дерева.
Рис.27. Дерево с линейным списком сыновей
Всякое дерево можно представить в виде бинарного дерева. При преобразовании сохраняется связь отца с самым левым (старшим) сыном. Они соединяются левой связью. Сыновья одного отца соединяются правыми
 |
связями. Рис. 28 поясняет преобразование.
Рис. 28. Преобразование дерева общего вида к бинарному дереву
Отметим, что преобразование является взаимно однозначным.
Контрольные вопросы
1) Дайте определение дерева.
2) Дайте определение бинарного дерева.
3) Применительно к деревьям определите понятия: корень, лист, степень узла, отец, сын, предок, потомок, брат.
4) Определите прямой, обратный и концевой порядок обхода бинарного дерева.
5) Напишите функцию, вычисляющую высоту бинарного дерева.
6) Какие преимущества даёт прошивка бинарного дерева?
7) Какие способы представления деревьев общего вида вы знаете?