Составители:
59
– с т р о г и е – вершины дерева имеют степень нуль (у листьев) или
два (у узлов);
– нестрогие – вершины дерева имеют степень нуль (у листьев),
один или два (у узлов).
В общем случае на k-м уровне двоичного дерева может быть до 2
k–1
вершин.
Двоичное дерево, содержащее только полностью заполненные уров-
ни (т. е. 2
k–1
вершин на каждом k-м уровне), называется п о л н ы м .
1.3.4.4. Реализация
Двоичное дерево можно реализовывать как статическую структуру
данных в виде одномерного массива, а можно как динамическую струк-
туру – в виде списка (рис. 17).
Строгое Нестрогое Полное
Неполное
1
2
3
Уровни
Рис. 16. Двоичное дерево
d4 d5
d3
d1
d2
d6
Указатель
на двоичное дерево
Двоичное
дерево
Динамическая
реализация
Статическая
реализация
d1
1
1 d1
2 d2
3 d3
4 d4
5 d5
6
7 d6
23
45 7
d2 d3
nil
d4
nil nil
d5
nil nil
d6
nil nil
Рис. 17. Двоичное дерево и его организация
Страницы
- « первая
- ‹ предыдущая
- …
- 57
- 58
- 59
- 60
- 61
- …
- следующая ›
- последняя »
