2015-05-13
1392
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ ТИПА «ДЕРЕВО»
Структуру данных типа «дерево» можно определить следующим образом:
Древовидная структура с базовым типом Т это либо пустая структура, либо узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т, называемых поддеревьями. Рассмотренная ранее структура данных типа «линейный разомкнутый список» может рассматриваться как вырожденное дерево.
 |
Дерево можно изобразить несколькими способами. Наиболее наглядный способ – в виде графа. В этом случае граф выглядит как перевернутое дерево (отсюда и название структуры – «дерево»):
Приведем несколько определений, связанных со структурами данного вида.
Верхний узел дерева называют узлом уровня 1 или корнем дерева. Далее номера уровней возрастают. Максимальный уровень дерева называют также глубиной или высотой дерева. В приведенном выше графе глубина дерева (максимальный уровень узлов дерева) равна четырем.
Два узла У (уровня k) и Х (уровня k+1) определяют следующим образом:
|
|
|
узел У считается предком узла Х, а узел Х – потомком узла У.
Если узел не имеет потомков, он называется терминальным узлом или листом. Все прочие узлы называют внутренними узлами.
Упорядоченное дерево – дерево, у которого ветви каждого узла упорядочены.
Приведенные ниже графы двух упорядоченных деревьев не идентичны (отличаются).
 |
Дерево, каждый узел которого имеет не более двух потомков, называют бинарным. По аналогии с этим троичное дерево – дерево, узлы которого не имеют более трех потомков. А дерево, отдельные узлы которого имеют более трех потомков, называют сильно ветвящимся.
Упорядоченное бинарное дерево – конечное множество элементов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями корня.
 |
Ниже приведен пример бинарного дерева:
Здесь:
A – корень дерева
B – корень левого поддерева дерева А
C – корень правого поддерева дерева А
D, G, H, I – листья
B – левый потомок дерева A
C – правый потомок дерева A
В программе на Паскале дерево представляется в виде иерархического списка, элемент которого (изображающий узел дерева) можно рассматривать как структуру следующего вида:
| Info | |
| Child | Next |
Здесь
Info – поле, содержащее полезную информацию
Child – ссылка на элемент-потомок
Next – ссылка на элемент того же уровня (на элемент, являющийся братом данного).
Ниже приведен пример упорядоченного дерева в виде графа и в виде иерархического списка:
 |
Это же дерево в программе можно представлено в виде следующей структуры:
|
|
|
 |
Бинарные деревья (как упорядоченные, так и нет) широко используются в программировании. По этой причине мы сосредоточимся в основном на рассмотрении процедур работы с ними.
Для описания узла бинарного дерева в программе введем тип, имеющий вид следующей записи:
 |
Приведем несколько процедур, иллюстрирующих работу с деревьями.
 |
Пример 1. Процедура создания нового узла.
Пример 2. Процедура создания потомка (поддерева).
 |
Пример 3. Создание бинарного дерева:
§ данные (целые числа) заносятся с клавиатуры;
§ дубликаты не включаются (но выводятся на экран);
§ признаком окончания ввода является ввод числа 0;
§ результат – бинарное упорядоченное дерево.
Примечание. В связи с ограниченными размерами страницы пособия текст программы разделен на две части.
|
Продолжение текста программы смотрите на следующей странице.
 |
