Министерство  образования и науки Российской Федерации

Федеральное агентство по образованию

      ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет информационных технологий

Кафедра управления и информатики в технических системах 
 

Задание на курсовую работу

Реализация  прикладной задачи с использованием пирамиды 
 

    Исходные  данные:   Массив, нелинейные структуры данных, пирамида.  

    Перечень  подлежащих разработке вопросов:

                           а) раскрыть понятие дерева;

                           б) охарактеризовать бинарные (двоичные) деревья;

                           в) ввести понятие  пирамиды;

                           г) изучить способы  реализации пирамиды;

                           д) реализовать сортировку на основе пирамиды. 

    Перечень  графического материала:

                           Рисунки, характеризующие  структуру дерева. 
 
 

    Дата  выдачи задания «___»______________200__ г.

    Руководитель 

    Исполнитель

    студент группы

    Срок  защиты работы «___»______________200__ г.

Аннотация 

    Курсовая  работа содержит 25 страниц, в том числе 3 рисунка, 1 таблица, 7 источников и 2 приложения. В данной курсовой работе изложена теория, связанная с понятием дерева, бинарных деревьев, двоичных деревьев поиска. Вводится понятие пирамиды, а так же программная реализация, основные операции (создание, удаление, добавление, обход и сортировки).

    В курсовой работе изложены основные понятия  деревьев и представлены способы  реализации пирамиды на практике. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание 
 
 
 
 
 
 
 

 

Введение 

    Как известно, деревья появились уже  на третий день сотворения мира и на протяжении веков древовидные структуры (особенно генеалогические деревья) очень широко применяются.  Как  математический объект понятие дерева было впервые формально определено в работе Г.Р. Кирхгофа. Он использовал свободные деревья для поиска набора фундаментальных циклов и электрической цепи, которые теперь носят его имя. Спустя десятки лет термин дерево появился в работах Артура Кэли. Он не знал о работах Кирхгофа, и свои исследования начал, изучив структуру алгебраических формул. Позднее Кэли продолжил их в основном для изучения задач. Древовидные структуры так же независимо изучались М.Э. Жорданом и К.И. Боркарелом.

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

    Целью данной курсовой работы является исследование одной из важных разновидностей деревьев – пирамиды.

    Для достижения данной цели нужно выполнить  следующие задачи:

1. раскрыть понятие дерева;
2. охарактеризовать бинарные (двоичные) деревья;
3. ввести понятие пирамиды;
4. изучить способы реализации пирамиды;
5. реализовать сортировку на основе пирамиды.

    Объектом  являются нелинейные структуры данных. Предметом исследования курсовой работы выступает одна из разновидностей двоичных деревьев – пирамида.

 

     1 Динамическая структура данных «Дерево»

1.1  Деревья

1.1.1 Определение. Основные понятия

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

    Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

    Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.

    Узлы  самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, они не имеют никаких потомков.

    Внутренний  узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.

    Поддерево — часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

    Высотой поддерева будем считать максимальную длину цепи y1, …,его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

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

При использовании  деревьев часто встречаются такие  понятия как путь между начальной и конечной вершиной (последовательность проходимых ребер или вершин).

2. Классификация деревьев

    Классификацию деревьев можно провести по разным признакам.

    1. По числу возможных потомков  у вершин различают двоичные (бинарные) или недвоичные (сильноветвящиеся) деревья.

Двоичное  дерево: каждая вершина может иметь  не более двух потомков.

Недвоичное  дерево: вершины могут иметь любое  число потомков.

На рисунке  1 представлены двоичное и недвоичное деревья.

 

Рисунок 1 – Двоичное и недвоичное деревья 

    2. Если в дереве важен порядок  следования потомков, то такие  деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:

    На  рисунке 2 представлены 2 простейших упорядоченных дерева.

    [2] Дональд Э. Кнут, Глава 2.3. Деревья. – Искусство программирования. — М.: Вильямс, 2000 — 832 с.

 

 

Рисунок 2 – Упорядоченные деревья

    1.2 Двоичные деревья

    1.2.1 Определение.  Основные понятия

    Двоичным  деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя.

    Элементы  дерева называются вершинами или  узлами, а соединения – ребрами  или дугами. От каждой вершины вниз идет не более двух ребер (поэтому дерево – двоичное). Вершины, с которыми соединена данная, и которые расположены ниже нее, называются детьми данной вершины (также часто говорят «сыновья»). При этом различаются правый и левый сын. Если вершина A является ребенком вершины B, то вершина B называется родителем A. У каждой вершины может быть не более одного родителя. Вершина, не имеющая родителя, называется корнем дерева. Вершины, не имеющие детей, называются листьями дерева. Все сказанное выше описывает двоичное дерево. На самом деле двоичное дерево – это математический объект и его можно определить строго. Одно из определений – рекурсивное – звучит так:

        - Каждая вершина имеет не более двух детей и не более одного родителя.

         - Одна вершина, не имеющая ни детей, ни родителей, является двоичным деревом.

    - Вершина, каждый из двух детей которой либо пуст, либо является двоичным деревом, тоже является двоичным деревом.

    Часть двоичного дерева, являющаяся двоичным деревом, называется поддеревом. Так для каждой вершины есть левое и правое поддеревья (возможно, пустые). 

    1.2.2 Программная реализация

    Существует  множество различных способов представления  деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве.

    PTree =^TTree;

    TTree =record

            Data: DataType; {элемент дерева}

            Left, Right: PTree; {указатели на поддеревья}

    End;

    Left, Right равны nil, если соответствующие поддеревья пусты. Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную:

    Var Tree: PTree

    Двоичное  дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее  значение узла, чем любой элемент  в левом поддереве, и меньшее  или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Важное свойство такого дерева: все элементы его различны. Название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n)=C*log2n (в худшем случае O(n)=n).