Стр. 10 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
8
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
А
А
Б
Б
Рис. 3. Различные бинарные деревья
Пусть бинарное дерево имеет высоту
h
. Следовательно, минимальное
число его вершин
1
min
+=
h n
.
1 2 2 ...
221
1
2
max
− = ++ ++=
+
h
h
n
Если дерево имеет
n
вершин то
1
max
−=
n h
,
)
2
1 ( log
2
min
+
=
n
h
.
Для представления бинарных деревьев обычно используются таблицы
размером
n
строк на 2 столбца.
Пусть λ – пусто.
Таблица 3
l
r
1
λ
λ
2
1
3
3
4
5
4
λ
λ
5
λ
λ
6
2
7
7
8
λ
8
λ
λ
Очевидно, такая таблица неудобна, если дерево подвергается
модификации (вставка, удаление, перемещение), или нумерация вершин не
сплошная, или вообще отсутствует. Поэтому в программе каждую строку
таблицы создают динамически, по мере необходимости. Она содержит два
указателя:
l
и
r
и всю остальную информацию, относящуюся к вершине.
Ещё один способ представления дерева – одномерный массив. Корню
дерева соответствует первая ячейка массива. Далее если некоторая вершина
P
хранится в ячейке с номером
i
, то её левый сын
l
P
хранится в ячейке с номером
i*
2, а правый сын
r
P
в ячейке
(i*
2
+
1
)
.
