Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Представление бинарного дерева в виде массива

Название: Представление бинарного дерева в виде массива
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 11:40:07 27 апреля 2011 Похожие работы
Просмотров: 2063 Комментариев: 2 Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать

ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА

Федеральное государственное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный университет водных коммуникаций»

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ

ДИСКРЕТНАЯ МАТЕМАТИКА

ТЕМА:

«ПРЕДСТАВЛЕНИЕ ДЕРЕВЬЕВ В ВИДЕ МАССИВА»

Выполнил студент 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 <fstream.h>

#include <stdio.h>

#include <conio.h>

#include <windows.h>

char bufRus[256];

char* Rus(const char* text){

CharToOem(text, bufRus);

return bufRus;

}

int main()

{ int i,k;

int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

cout << Rus("Дерево:") << endl;

cout << Rus("Корень дерева - a[0] = ") << a[0] << endl;

k=0;

for (i=1; i<=14; i++)

{

if (i%2==0) k=k+1;

if (i%2!=0) cout << Rus(" левый сын узла a[") << i-k-1 << "]=" << a[i] << endl;

if (i%2==0) cout << Rus(" правый сын узла a[") << i-k-1 << "]=" << a[i] << endl;

}

return 0;


Результат выполнения программы:


Список литературы

1) Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.

2) Д. Райли Абстракция и структуры данных. Вводный курс.

3) Д. Кнут Искусство программирования для ЭВМ. Т1, Основные алгоритмы.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:43 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:39 29 ноября 2015

Работы, похожие на Курсовая работа: Представление бинарного дерева в виде массива
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Дерево сортировки - бинарное дерево, каждый узел которого содержит ключ и обладает следующим свойством: значения ключа во всех узлах левого поддерева меньше, а во всех узлах ...
у вершины v два сына; в этом случае находим в левом поддереве вершины v наибольший элемент b, рекурсивно удаляем из этого поддерева вершину, содержащую b, и присваиваем вершине v ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4177 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Алгоритмический язык Паскаль
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ...
1) элемент дерева - ВЕРШИНА, из которого связи только выходят, называют КОРНЕМ дерева (в нашем случае А);
Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 2870 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать
Проектирование трансляторов
ЛЕКЦИЯ 1 СУЩНОСТЬ ПРЕДМЕТА. СОДЕРЖАНИЕ КП. СРОКИ. ОРГАНИЗАЦИЯ РАБОТ. МАТЕМАТИЧЕСКИЙ АППАРАТ. СТРУКТУРНАЯ СХЕМА ТРАНСЛЯТОРА. ПРОХОДЫ ТРАНСЛЯТОРА ...
соответствует поддереву, оператор триады - корень поддерева, опе-
обход левого поддерева сверху;
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 655 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э-о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного ...
БИНАРНОЕ ДЕРЕВО - э-о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1147 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Экспертные системы. Классификация экспертных систем. Разработка ...
db_dan(""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°",7605,"ГЁ" db_dan("Ѭ*Ѭ"",1165,""°ў аЁйҐбвў° ЇаҐ$ЇаЁЁ= вҐ"Ґ°" db_dan("ѬѬ"*",7094,"Ѭ*Ѭ"" db_dan("-"*",8205,"ѬѬ ...
Листья дерева (узлы, образующие его нижний "ярус"), соответствуют фактам, истиностные значения которых запрашиваются у пользователя, или первоначально известным фактам из базы ...
Деревом называется граф, каждая вершина которого имеет ровно одну непосредственно предшествующую ей (родительскую) вершину, за исключением выделенной вершины, называемой корнем ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 34031 Комментариев: 7 Похожие работы
Оценило: 10 человек Средний балл: 4.5 Оценка: 5     Скачать
Реализация АВЛ-деревьев через классы объектно-ориентированного ...
Министерство образования и науки Украины Запорожская государственная инженерная академия Кафедра программного обеспечения автоматизированных систем ...
Все операции идентичны описанным для бинарных деревьев, за исключением методов Insert и Delete, которые должны постоянно отслеживать соотношение высот левого и правого поддеревьев ...
Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить ...
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 1575 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Разработка экстремальных туристских маршрутов на Российском Севере (по ...
Министерство образования Российской Федерации Сочинский государственный университет туризма и курортного дела Институт туристского и гостиничного ...
Водораздельный хребет простирается на юго-запад более чем на 200 км.Поперечными долинами хребет разделен на массивы (Рай-Из, Пай-Ер, Войкар-Сыньинсикй) с абсолютными высотами 1100 ...
ГУГК 1988 г.), понятия "правый" и "левый" употребляются в орографическом смысле, из многочисленных вариантов названий перевалов и вершин выбраны наиболее часто употребляемые.
Раздел: Рефераты по туризму
Тип: реферат Просмотров: 5444 Комментариев: 6 Похожие работы
Оценило: 8 человек Средний балл: 3.8 Оценка: 4     Скачать
Анализ алгоритмов нечисленной обработки данных
... рассмотрению и изучению алгоритмов нечисленной обработки данных - линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом.
Ветвью дерева называют поддерево, состоящее из некоторой дуги данного дерева, ее начальной и конечной вершин, а также всех вершин и дуг, лежащих на всех путях, выходящих из ...
Локальные переменные: k - количество узлов в дереве, m - количество перестановок, i1 - индекс элемента в дереве (массиве).
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Просмотров: 108 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Представление бинарного дерева в виде массива (4494)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151195)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru