ФЕДЕРАЛЬНОЕАГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА
Федеральноегосударственное образовательное учреждение высшего профессиональногообразования
«Санкт-Петербургскийгосударственный университет водных коммуникаций»
КУРСОВАЯРАБОТА ПО ДИСЦИПЛИНЕ
ДИСКРЕТНАЯМАТЕМАТИКА
ТЕМА:
«ПРЕДСТАВЛЕНИЕДЕРЕВЬЕВ В ВИДЕ МАССИВА»
Выполнилстудент 2 курса
группыИП-21:
МальцевВалерий
Проверил:
НырковАнатолий Павлович
Санкт-Петербург
2009г.
Содержание
Деревья. 3
Терминология деревьев. 4
Бинарныедеревья. 5
Представление бинарныхдеревьев. 9
Приложение. 12
Текст программы… 13
Списоклитературы… 15
Деревья
Массивыи связанные списки определяют коллекции объектов, доступ к которымосуществляется последовательно. Такие структуры данных называют линейными(linear) списками, поскольку они имеют уникальные первый и последний элементы иу каждого внутреннего элемента есть только один наследник. Линейный списокявляется абстракцией, позволяющей манипулировать данными, представляемымиразличным образом — массивами, стеками, очередями и связанными списками.
Вомногих приложениях обнаруживается нелинейный порядок объектов, где элементымогут иметь нескольких наследников. Например, в фамильном дереве родитель можетиметь нескольких потомков (детей). На Рис. 1 показаны три поколения семьи.Такое упорядочение называют иерархическим.
/>
Рис.1.
Вэтой статье мы рассмотрим нелинейную структуру, называемую деревом (tree),которая состоит из узлов и ветвей и имеет направление от корня к внешним узлам,называемым листьями. Эти структуры подобны коммуникационной сети, показанной наРис. 2, требуют особых алгоритмов и применяются в специальных приложениях.
/>
Рис.2 Терминология деревьев
Древовиднаяструктура характеризуется множеством узлов (nodes), происходящих отединственного начального узла, называемого корнем (root). На Рис. 3 корнемявляется узел А. В терминах генеалогического дерева узел можно считатьродителем (parent), указывающим на 0, 1 или более узлов, называемых сыновьями(children). Например, узел В является родителем сыновей E и F. Родитель узла H- узел D. Дерево может представлять несколько поколений семьи. Сыновья узла исыновья их сыновей называются потомками (descendants), а родители и прародители– предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B.Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом(leaf).
Каждыйузел дерева является корнем поддерева (subtree), которое определяется даннымузлом и всеми потомками этого узла. Узел F есть корень поддерева, содержащегоузлы F, I и J. Узел G является корнем поддерева без потомков. Это определениепозволяет говорить, что узел A есть корень поддерева, которое само оказываетсядеревом.
/>
Рис.3.
Переходот родительского узла к дочернему и к другим потомкам осуществляется вдоль пути(path). Например, на Рис. 4 путь от корня A к узлу F проходит от A к B и от B кF. Тот факт, что каждый некорневой узел имеет единственного родителя,гарантирует, что существует единственный путь из любого узла к его потомкам.Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0.Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-гоуровня и т.д. Например, на Рис. 4 узел F является узлом 2-го уровня с длинойпути 2.
Глубина(depth) дерева есть его максимальный уровень. Понятие глубины также может бытьописано в терминах пути. Глубина дерева есть длина самого длинного пути откорня до узла.
НаРис.4 глубина дерева равна 3.
/>
Рис.4.Уровень узла и длина путиБинарныедеревья
Хотядеревья общего вида достаточно важны, мы сосредоточимся на ограниченном класседеревьев, где каждый родитель имеет не более двух сыновей (Рис. 5). Такиебинарные деревья (binary trees) имеют унифицированную структуру, допускающуюразнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучениебинарных деревьев дает возможность решать наиболее общие задачи, связанные сдеревьями, поскольку любое дерево общего вида можно представить эквивалентнымему бинарным деревом.
Укаждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлуслева будем употреблять термин левый сын (left child), а по отношению к узлусправа – правый сын (right child). Наименования «левый» и«правый» относятся к графическому представлению дерева. Бинарноедерево является рекурсивной структурой. Каждый узел – это корень своегособственного поддерева. У него есть сыновья, которые сами являются корнями деревьев,называемых левым и правым поддеревьями соответственно. Таким образом, процедурыобработки деревьев рекурсивны. Вот рекурсивное определение бинарного дерева:
Бинарноедерево — это такое множество узлов B, что
а)B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);
б)B разбивается на три непересекающихся подмножества:
· {R}корневой узел
· {L1,L2, ..., Lm} левое поддерево R
· {R1,R2, ..., Rm} правое поддерево R
Налюбом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящеесяна уровень, является показателем плотности дерева. Интуитивно плотность естьмера величины дерева (число узлов) по отношению к глубине дерева. На Рис. 5дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5узлов при глубине 4. Последний случай является особой формой, называемойвырожденным (degenerate) деревом, у которого есть единственный лист (E) икаждый нелистовой узел имеет только одного сына. Вырожденное деревоэквивалентно связанному списку.
/>
Рис.5.Бинарные деревья
Деревьяс большой плотностью очень важны в качестве структур данных, так как онисодержат пропорционально больше элементов вблизи корня, т.е. с более короткимипутями от корня. Плотное дерево позволяет хранить большие коллекции данных иосуществлять эффективный доступ к элементам. Быстрый поиск – главное, чтообусловливает использование деревьев дляхранения данных.
Вырожденныедеревья являются крайней мерой плотности. Другая крайность – законченныебинарные деревья (complete binary tree) глубины N, где каждый уровень 0...N — 1имеет полный набор узлов, и все листья уровня N расположены слева. Законченноебинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6показаны законченное и полное бинарные деревья.
/>/>
Рис.6.Классификация бинарных деревьев
Бинарныедеревья классифицируются по нескольким признакам. Введем понятия степени узла истепени дерева. Степенью узла в дереве называется количество дуг, которое изнего выходит. Степень дерева равна максимальной степени узла, входящего вдерево. Исходя из определения степени понятно, что степень узла бинарногодерева не превышает числа два. При этом листьями в дереве являются вершины,имеющие степень ноль.
/>
Рис.7.Бинарное дерево
Другимважным признаком структурной классификации бинарных деревьев является строгостьбинарного дерева. Строго бинарное дерево состоит только из узлов, имеющихстепень два или степень ноль. Нестрого бинарное дерево содержит узлы состепенью равной одному.
/>
Рис.8.Полное и неполное бинарные деревья
/>
Рис.9.Строго и не строго бинарные деревья/>Представление бинарных деревьев
Бинарныедеревья достаточно просто могут быть представлены в виде списков или массивов.Списочное представление бинарных деревьев основано на элементах,соответствующих узлам дерева. Каждый элемент имеет поле данных и два поляуказателей. Один указатель используется для связывания элемента с правымпотомком, а другой с левым. Листья имеют пустые указатели потомков. При такомспособе представления дерева обязательно следует сохранять указатель на узел,являющийся корнем дерева.
Можнозаметить, что такой способ представления имеет сходство с простыми линейнымисписками. И это сходство не случайно. На самом деле рассмотренный способпредставления бинарного дерева является разновидностью мультисписка,образованного комбинацией множества линейных списков. Каждый линейный списокобъединяет узлы, входящие в путь от корня дерева к одному из листьев.
/>
Рис.10.Представление бинарного дерева в виде списковой структуры
Ввиде массива проще всего представляется полное бинарное дерево, так как оновсегда имеет строго определенное число вершин на каждом уровне. Вершины можнопронумеровать слева направо последовательно по уровням и использовать этиномера в качестве индексов в одномерном массиве.
/>
Рис.11.Представление бинарного дерева в виде массива
Есличисло уровней дерева в процессе обработки не будет существенно изменяться, тотакой способ представления полного бинарного дерева будет значительно болееэкономичным, чем любая списковая структура.
Однакодалеко не все бинарные деревья являются полными. Для неполных бинарных деревьевприменяют следующий способ представления. Бинарное дерево дополняется до полногодерева, вершины последовательно нумеруются. В массив заносятся только тевершины, которые были в исходном неполном дереве. При таком представленииэлемент массива выделяется независимо от того, будет ли он содержать узелисходного дерева. Следовательно, необходимо отметить неиспользуемые элементымассива. Это можно сделать занесением специального значения в соответствующиеэлементы массива. В результате структура дерева переносится в одномерныймассив. Адрес любой вершины в массиве вычисляется как
адрес= 2к-1+i-1,
гдеk-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрескорня будет равен единице. Для любой вершины можно вычислить адреса левого иправого потомков
адрес_L= 2к+2(i-1)
адрес_R= 2к+2(i-1)+1
Главнымнедостатком рассмотренного способа представления бинарного дерева является то,что структура данных является статической. Размер массива выбирается исходя измаксимально возможного количества уровней бинарного дерева. Причем чем менееполным является дерево, тем менее рационально используется память.
Приложение
Вкачестве примера использования бинарного дерева в виде массива был использованмассив – a[ i ], состоящий из 15 элементов (от 1 до 15). В результате дереводолжно иметь вид:
/>
Текст программы
дерево нелинейное массив бинарное
#include
#include
#include
#include
charbufRus[256];
char*Rus(const char* text){
CharToOem(text,bufRus);
returnbufRus;
}
intmain()
{ inti,k;
inta[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
cout
cout
k=0;
for(i=1; i
{
if(i%2==0) k=k+1;
if(i%2!=0) cout
if(i%2==0) cout
}
return0;
Результатвыполнения программы:
/>
Список литературы
1) Ахо А.,Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.
2) Д.Райли Абстракция и структуры данных. Вводный курс.
3) Д.Кнут Искусство программирования для ЭВМ. Т1, Основные алгоритмы.