Стр. 9 - Основы алгоритмов и структур данных

Содержание 7
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Каждое поддерево является полноценным деревом.
1 и 5 – сыновья отца 3.
Существенно следующее. В дереве явно задают указатели на сыновей
каждой вершины и никогда не задают указатель на отца.
4,6,2,7,8,9 – потомки предков 5 и 3.
1,2 ,7 – листья дерева.
Если в дереве n вершин то у него (n-1) дуга. В каждую вершину входит
одна дуга, кроме корня. Каждый лист дерева имеет ранг 1. Удалим листья.
Получившиеся листья у дерева имеют ранг 2 и т.д.
Таблица 1
Ранг Вершины
1 1,2,7,8,9
2 4,6
3 5
4 3
Уровень корня дерева – 0.
Уровень любой другой вершины V определяется по формуле.
Уровень(V) = Уровень(отец(V)) +1.
Таблица 2
Уровень Вершины
0 3
1 1,5
2 4,6
3 2,7,8,9
Высота дерева - это максимальный уровень его вершин.
Высота дерева - это максимальное число рёбер на пути от корня до листа.
Высота дерева - это максимальное из высот его поддеревьев + 1. (высота
дерева из одной вершины - это 0).
Двоичным или бинарным называется дерево, каждая вершина которого
имеет не более двух сыновей (бинарным называется дерево имеющее, не более
двух бинарных поддеревьев).
В бинарных деревьях различают левых и правых сыновей, левых и правых
потомков и поддеревьев.