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

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

— каждый элемент дерева связан только с одним предыдущим элементом, Любой узел дерева может быть промежуточным либо терминальным (листом). На рис. 4.2 промежуточными являются элементы M1, M2, листьями — A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей.
Высота — это количество уровней дерева. У дерева на рис. 4.2 высота равна двум.
Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рис. 4.2 для M1 степень исхода 2, для М2 — 3). По степени исхода классифицируются деревья:
1) если максимальная степень исхода равна m, то это — m-арное дерево;
2) если степень исхода равна либо 0, либо m, то это — полное m-арное дерево;
3) если максимальная степень исхода равна 2, то это — бинарное дерево;
4) если степень исхода равна либо 0, либо 2, то это — полное бинарное дерево.
Для описание связей между узлами дерева применяют также следующую терминологию: М1 — “отец” для элементов А и В. А и В — “сыновья” узла М1.

4.1.1 Представление  деревьев

Наиболее удобно деревья представлять в памяти ЭВМ в виде связанных списков. Элемент списка должен содержать информационные поля, в которых содержится значение узла и степень исхода, а также — поля-указатели, число которых равно степени исхода (рис4.3). То есть, любой указатель элемента ориентирует данный элемент-узел с сыновьями этого узла.

4.2   Бинарные деревья

Бинарные деревья являются наиболее используемой разновидностью деревьев.
Согласно представлению деревьев в памяти ЭВМ каждый элемент будет записью, содержащей 4 поля. Значения этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.
При построении необходимо помнить, что левый сын имеет ключ меньший, чем у отца, а значение ключа правого сына больше значения ключа отца. Например, построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79. Оно имеет следующий вид:

Получили упорядоченное бинарное дерево с одинаковым числом уровней в левом и правом поддеревьях. Это — идеально сбалансированное дерево, то есть дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не более чем на единицу.
Для создания бинарного дерева надо создавать в памяти элементы типа (рис. 4.5):

Операция V = MakeTree(Key, Rec) — создает элемент (узел дерева) с двумя указателями и двумя полями (ключевым и информационным) .

Вид процедуры MakeTree:
Псевдокод
p = getnode
r(p) = rec
k(p) = key
v = p
left(p) = nil
right(p) = nil
Паскаль
New(p);
p^.r := rec;
p^.k := key;
v := p;
p^.left := nil;
p^.right := nil;

4.2.1  Сведение m-арного дерева к бинарному
Неформальный алгоритм:

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

Страницы: 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

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