ДЕРЕВЬЯ

15. ДЕРЕВЬЯ

15.1 Характеристика древовидной структуры данных

Указанные выше составные структуры не всегда удобны в работе, т.к. в начале сложного списка стоит дек, состоящий из звеньев, каждое из которых "смотрит" на свой линейный список. Поэтому при представлении составных структур удобнее задавать звенья этого списка в виде дерева, которое допускает ответвления в каждом звене, а само дерево, как стек, начинается с вершины.

Существует несколько способов изображения деревьев: вложения множеств, скобок, графы.

При ВЛОЖЕНИИ МНОЖЕСТВ используются хорошо известные в математике диаграммы Венна. Способ изображения дерева в виде ВЛОЖЕНИЯ СКОБОК менее нагляден, например, A(В(D,E)), C(F,G,H)).

Рассмотрим терминологию, присущую представлению дерева в виде графа:

1) элемент дерева - ВЕРШИНА, из которого связи только выходят, называют КОРНЕМ дерева (в нашем случае А);

2) связи между элементами дерева называются РЕБРАМИ;

3) если вершина В находится на графе ниже А, то В называется ПОТОМКОМ, а А - ПРЕДКОМ В;

4) каждая вершина находится на своем УРОВНЕ, причем корню соответствует 0-й уровень;

5) число уровней (или максимальный уровень) называют ВЫСОТОЙ или ГЛУБИНОЙ дерева;

6) если вершина не имеет потомков, то она называется ЛИСТОМ (в нашем примере F,G,H,D,E - листы);

7) вершины, лежащие между корнем и листьями, называют ВНУТРЕННИМИ.

Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо признаку. Для деревьев, элементами (вершинами) которых являются целые числа, упорядоченность устанавливается по возрастанию (убыванию) элементов.

Так, если дерево упорядочено по возрастанию, это означает, что самое левое ребро на графе заполнено наименьшим числом.

НАПРИМЕР:

5

/ \

3 10

/ \ / \

2 4 9 12

2 < 3 < 5 < 10 < 12; 2 < 3 < 4;

3 < 10;

2 < 4 < 9 < 12; 9 < 10 < 12.

Особый интерес представляют деревья, у которых из каждой вершины может исходить не более 2-х (т.е. ни одного, одно или два) ребер. Такие деревья называют ДВОИЧНЫМИ или БИНАРНЫМИ, либо деревьями 2-й степени.

Итак, степень дерева - это максимальное количество ребер, исходящих из каждой вершины. Например, нижеследующий граф определяет дерево 3-й степени:

R

/ \

O W

/ | \ \

E Q X H

Бинарное дерево принято также называть ГЕНЕАЛОГИЧЕСКИМ:

X -внук

/ \

сын - Y Z -дочь

/ \ / \

A B C D

мать отец мать отец

ОПРЕДЕЛЕНИЕ: дерево называется ПРЕДЕЛЬНО (ИДЕАЛЬНО) СБАЛАНСИРОВАННЫМ, если разница между числом вершин в его левых и правых поддеревьях (на всех уровнях) не более 1.

15.2 Построение идеально сбалансированного дерева

Для построения такого дерева используется рекурсивное правило:

Пусть требуется построить дерево из N элементов (вершин).

Выберем один из них в качестве корня.

2. Строим левое поддерево с количеством вершин NL = N div 2.

3. Так же строим правое поддерево с числом вершин NR = N-NL-1.

Например, при построении дерева из 5 элементов:

1) один элемент идет на корень;

2) оставшиеся 4 элемента разбиваются на два поддерева:

NL = 2 и NR = 2;

3) в каждом из поддеревьев один элемент идет на корень, а другой - на лист: NL1= 1, NR1= 0.

Очевидно, что для отображения структуры дерева в память ЭВМ требуется построение динамических объектов.

Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.

Отсюда следует процедура-функция формирования дерева, где используется указанный выше принцип построения рекурсивной функции.

У данной процедуры в качестве параметра-аргумента выступает число элементов (вершин) дерева, а значением функции является ссылка - указатель на следующую вершину (левую и правую). Сами элементы запрашиваются с клавиатуры:

function FORMIRTREE (N: integer): SS;

var Z: SS; NL, NR: integer;

begin

¦ if N = 0 then Z:= nil {Пустое дерево}

¦ else

¦ begin

¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);

¦ ¦ write('Ввести вершину'); readln(Z^.k);

¦ ¦ Z^.right:= FORMIRTREE (NR);

¦ end;

¦ FORMIRTREE:= Z; {Запоминание ссылки на корень дерева}

end.

ПОЯСНЕНИЕ. Сначала все N-1 элементов разбиваем на две части - левую и правую. Затем каждую часть соответственно делим на две. Рекурсия прекращается, когда N становится равным нулю - деление закончено, последняя образованная ссылка указывает на корневой элемент:

Дерево имеет 2 уровня, на нижнем (втором) уровне располагаются только левые листы (правые отсутствуют из-за нехватки элементов).

Чтобы вывести дерево на экран дисплея, необходимо предусмотреть обход этого дерева по принципу его создания, т.е. в виде рекурсивной процедуры:

procedure PRINTTREE (Z: ss; X: integer; var Y: integer);

var I: integer;

begin

¦ Y:= (X-5)/5 - 1;{ Подсчет числа уровней }

¦ if Z <> nil then

¦ begin

¦ ¦ PRINTTREE(Z^.right, X+5, Y);

¦ ¦ for I:=1 to X do write(' ');

¦ ¦ writeln(Z^.k);

¦ writeln;

¦ ¦ PRINTTREE(Z^.left, X+5, Y);

¦ end;

end.

ЗАМЕЧАНИЕ. Эта рекурсивная процедура выводит на экран элементы слева направо, причем крайним левым элементом оказывается корень дерева. Между соседними уровнями процедура печатает 5 пробелов, а между элементами одного уровня - одну строчку. В процедуре параметр Y, как выходной, служит для указания числа уровней построенного дерева. Формула (X-5)/5-1 дает число уровней, т.к. по построению между элементами соседних уровней находится 5 пробелов, а в завершение работы этой процедуры последним печатается самый левый (самый нижний и, значит, самый удаленный от левого края экрана) лист дерева:

Теперь, имея рекурсивную функцию FORMIRTREE формирования дерева и рекурсивную процедуру PRINTTREE печати его элементов, можно записать основную программу построения и печати дерева с указанным числом вершин.

program TREE;

type SS = ^ZVENO;

ZVENO = record

K: integer;

left, right: SS;

end;

var KOL: integer; Y: REAL; DER: SS;

{KOL - число элементов дерева; DER - ссылка на корень дерева}

< рекурсивная функция FORMIRTREE формирования дерева>;

< рекурсивная процедура PRINTTREE печати дерева>;

begin

¦ write('Введите число элементов дерева');

¦ y:= 0; {Число уровней дерева}

¦ readln (KOL); DER:= FORMIRTREE (KOL);

¦ writeln; writeln(' Д Е Р Е В О:');

¦ PRINTTREE (DER, 5, y); writeln;

¦ writeln(' Всего', y:3:0,' уровня(ей) дерева.');

end.

ПОЯСНЕНИЕ. Дерево, состоящее из пяти элементов (1,2,3,4,5), будет выведено на экран в виде следующего графа:

ДЕРЕВО

Похожие работы

Основы программирования на языке Паскаль

Скачать

168304

7

26

... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы   6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Алгоритмические языки и программирование Системное программное обеспечение Технология программирования"

Скачать

112819

0

0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Основные понятия алгоритмического языка

Скачать

91405

0

0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...