МИНИСТЕРСТВО  ОБРАЗОВАНИЯ и науки УКРАИНЫ

Донецкий  государственный  институт искусственного интеллекта 

Д080403.1.01.01/077.КП

Кафедра программного обеспечения

интеллектуальных  систем 
 
 
 
 
 

КУРСОВОЙ  ПРОЕКТ

по дисциплине: «Структуры и организация данных в ЭВМ»

на тему: «Работа с двоичными деревьями: построение, поиск, удаление, включение и обход» 
 
 
 
 
 
 

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

      ст.преп. Маслова Е.А.

  ^{(дата, подпись)}

асс. Митькина А.М.

        ^{(дата, подпись)}

     Разработал:

ст.гр. ПО-01 А.В.

     ^{(дата, подпись)}

Нормоконтроль:

асс. Митькина А.М.

        ^{(дата, подпись)} 
 
 

2002

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ  УКРАИНЫ

ДОНЕЦКИЙ  ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА 

      Факультет:  Современных      компьютерных        информационных

  технологий

      Кафедра: Программного обеспечения интеллектуальных систем

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

по дисциплине “Структуры и организация данных на ЭВМ ” 

 

Дата выдачи задания                 24 сентября 2002 г.    

Дата защиты проекта.                26 декабря 2002 г.    

Руководитель   ст. преп. Маслова Елена Александровна    

                              ^{(должность,  Ф.И.О.)             (подпись)}

                    асс. Митькина  Анна Михайловна           

                              ^{(должность,  Ф.И.О.)              (подпись)}

Разработчик    ст. гр. ПО-01б Ружицкий Андрей Владиславович  __________

                              ^{(должность,  Ф.И.О.)              (подпись)} 

 

 
 

ВВЕДЕНИЕ

 
 

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

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

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

 

1 ТЕРЕТИЧЕСКИЕ ДАННЫЕ

 

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

     На  рис. 1.1 показано дерево. Корневой узел A связан с тремя поддеревьями, начинающимися в узлах B, C и D. Узлы B, C и D связаны с поддеревьями с корнями E, F и G соответственно, узел G , в свою очередь связан с поддеревьями H, I и J.

     

       
 
 
 
 
 
 
 
 
 

     Рисунок 1.1 - Дерево 

     Терминология  деревьев представляет собой смесь  терминов, позаимствованных из ботаники и генеалогии. Из ботаники пришли термины, такие как узел (node), определяемый как точка, в которой может начинаться ветвление, ветвь (branch), определяемая как связь между двумя узлами, и лист (leaf) — узел, из которого не выходят другие ветви.

     Из  генеалогии пришли термины, которые описывают родство. Если один узел находится непосредственно над другим, верхний узел называется родителем (parent), а нижний дочерним узлом (child). Узлы на пути вверх от узла до корня называются предками (ancestors) узла. Например, на рис. 1.1 узлы G, D и A — это все предки узла I.

     Узлы, которые находятся ниже какого-либо узла дерева, называются потомками (descendants) этого узла. Узлы G, H, I и J на рис. 1.1 — это все потомки узла D.

     Иногда  узлы, имеющие одного родителя, называются узлами-братьями или узлами-сестрами (sibling nodes).

     Существует  еще несколько терминов, которые не пришли из ботаники или генеалогии. Внутренним узлом (internal node) называется узел, который не является листом. Порядком узла (node degree) называется число его дочерних узлов. Порядок дерева — это наибольший порядок его узлов. Дерево на рис. 1.1 — третьего порядка, потому что узлы с наибольшим порядком, узлы A и G, имеют по 3 дочерних узла.

     Глубина (depth) узла равна числу его предков плюс 1. На рис. 1.1 глубина узла С равна 2. Глубиной (depth) или высотой (height) дерева называется наибольшая глубина его узлов. Глубина дерева на рис. 1.1 равна 4. Плотность – мера величины дерева (число узлов по отношению к глубине дерева). Дерево с большей плотностью хранит больше элементов вблизи корня, поэтому доступ к элементам более эффективен.

     Дерево 2 порядка называется двоичным деревом (binary tree). Деревья третьего порядка иногда называются троичными (ternary) деревьями. Более того, деревья порядка N иногда называются N-ичными (N-ary) деревьями.

     Дерево  порядка 12, например, называется 12-ричным (12-ary) деревом, а не додекадеричным (dodecadary) деревом. Некоторые избегают употребления лишних терминов и просто говорят «деревья 12 порядка».

      Полное  дерево (complete tree) содержит максимально возможное число узлов на каждом уровне, кроме нижнего. Все узлы на нижнем уровне сдвигаются влево. Например, каждый уровень троичного дерева содержит в точности три дочерних узла, за исключением листьев, и возможно, одного узла на один уровень выше листьев. На рис. 1.2 показаны полные двоичное и троичное деревья. 

     Рисунок 1.2 – Полные двоичное и троичное деревья 

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