- •1. Понятие структур данных и алгоритмов
- •3. Системы счисления. Непозиционные/позиционные системы счисления. Изображение чисел в позиционной системе счисления. Перевод чисел из одной системы счисления в другую.
- •8. Битовые типы
- •2.7.1. Физическая структура указателя
- •17. Записи.
- •21. Операции логического уровня над статическими структурами. Сортировка
- •22. Характерные особенности полустатических структур
- •23. Стеки Логическая структура стека
- •4.2.2. Машинное представление стека и реализация операций
- •24. Очереди fifo
- •25. Деки
- •4.4.2. Деки в вычислительных системах
- •26. Строки. Логическая структура строки
- •4.5.3. Представление строк в памяти.
- •27. Связное представление данных в памяти
- •28. Графы
- •29. Деревья Основные определения
- •30. Бинарные деревья.
- •31. Основные операции над деревьями.
- •Процессы разработки программ
- •V-образный жизненный цикл;
- •Процессы и документы при разработке пс
30. Бинарные деревья.
Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.
При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.
На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное дерево, а на 6.12(c) показаны все четыре возможных расположения сыновей некоторой вершины бинарного дерева.
Рис. 6.13. Изображения бинарных деревьев
В позиционном бинарном дереве каждая вершина представлена единственным образом посредством строки символов над алфавитом {0,1}, при этом корень характеризуется пустой строкой. Любой сын вершины "u" характеризуется строкой, префикс (начальная часть) которой является строкой, характеризующей "u". Примером бинарного дерева является фамильное дерево с отцом и матерью человека в качестве его потомков. Еще один пример - это арифметическое выражение с двухместными операциями, где каждая операция представляет собой ветвящийся узел с операндами в качестве поддеревьев.
Представление любого дерева, леса бинарными деревьями. Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.
Правило построения бинарного дерева из любого дерева:
1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
2. Соединить горизонтальными ребрами всех братьев одного отца;
3. Таким образом перестроить дерево по правилу:
левый сын - вершина, расположенная под данной;
правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные - правых.
В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.
В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.
Рис.6.14. Исходное дерево
Рис.6.15 Промежуточный результат перестройки дерева
Рис. 6.16. Представление дерева в виде бинарного
Описанный выше метод представления произвольных упорядоченных деревьев посредством бинарных деревьев можно обобщить на представление произвольного упорядоченного леса.
Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану: в начале поддерево с корнем А, затем В и затем Н. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.
Машинное представление деревьев в памяти ЭВМ.
Деревья можно представлять с помощью связных списков и массивов (или последовательных списков). Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:
LPTR |
DATA |
RPTR |
где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.