Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

каждый элемент дерева связан только с одним предыдущим элементом.
Каждый узел дерева может быть промежуточным (элементы 2,3,5,7) либо терминальным («листом» дерева) (элементы 4,9,10,11,8,6). Характерной особенностью терминальных узлов является отсутствие ветвей.

Элемент Y, находящийся непосредственно ниже элемента X, называется непосредственным потомком X, если X находится на уровне i , то говорят, что Y лежит на уровне i+1.
Считается, что корень лежит на уровне 0.
Число непосредственных потомков элемента называется его степенью исхода, в зависимости от степени исхода узлов деревья классифицируют :
A) Если степень исхода узлов — М, то дерево называется М-арным ;
B) Если степень исхода узлов — М или 0, то — полное М-арное дерево;
C) Если степень исхода узлов дерева равна 2, то дерево называется бинарным ;
D) Если степень исхода равна 2 или 0, то — полное бинарное дерево.
Особенно важную роль играют бинарные деревья, далее мы будем рассматривать их более подробно.

Представление деревьев в памяти ЭВМ

Деревья наиболее удобно представлять в памяти ЭВМ в виде связанных нелинейных списков. Элемент должен содержать INFO-поле, где содержится характеристика узла. Следующее поле определяет степень исхода узла и количество полей указателей равное степени исхода. Каждый указатель элемента ориентирует данный элемент-узел с его сыновьями. Узлы, в которые входят стрелки от исходного элемента, называются его сыновьями.
INFO-поле содержит два поля : поле записи (rec) и поле ключа (key). Ключ задается числом, по ключу определяют место элемента в дереве.

Сведение М-арного дерева к бинарному

1. В каждом узле дерева отсекают все ветви, кроме крайних левых, соответствующих старшим сыновьям;
2. Соединяют горизонтальными линиями сыновей одного родителя (узла);
2.Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.

Построение бинарных деревьев

Согласно представлению деревьев в памяти ЭВМ каждый элемент (узел бинарного дерева) будет записью, содержащей четыре поля. Значением этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.
При построении необходимо помнить, что левый сын имеет ключ меньше чем отец (родитель). Значение ключа правого сына больше значения ключа отца.
Например, узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101.
Бинарное дерево будет иметь вид:

Получили упорядоченное бинарное дерево с минимальным числом уровней.
Идеально сбалансированное дерево — это дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не больше, чем на единицу.

Алгоритм
Процедура создания бинарного дерева

Для построения дерева необходимо создать в памяти ЭВМ элемент следующего типа:

P, Q — рабочие указатели
V=maketree(key,rec) — процедура, которая создает сегмент ключа и записи
P=getnode — генерация нового элемента
r=rec
k=key
V=P
left=nil
right=nil
tree — указатель на корень дерева

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники