Двоичные деревья и их роль в информатике
Курсовая работа, 05 Октября 2010, автор: Марья Иванова
Описание работы
Впервые понятие «дерево» ввел физик Густав Кирхгофф в 1847 году. Будучи студентом Кенигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены, как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются не зависимыми, и Кирхгофф использовал деревья для получения независимого подмножества уравнений.
В последние десять лет компьютерная наука столкнулась с тем, что деревья обеспечивают удобные структуры для хранения и исправления определенных типов данных – так называемых иерархических баз данных.
Корневые деревья интенсивно используются в информатике. Деревья являются самым распространенным классом графов, применяемых в программировании. Наиболее важные применения деревьев этого типа связаны с представлением и сортировкой данных. Некоторые другие важные применения корневых деревьев в компьютерной науке связаны с представлением алгебраических выражений.
Обычным и важным действием при обработке данных является сортировка данных в соответствии с определенным критерием. Природа данных и цели их использования определяют особенности сортировки. Чаще всего приходится иметь дело с числовой или буквенной сортировкой. Предположим, что отношение представляет собой тотальный порядок, то есть такой порядок, при котором для любой пары элементов возможно сравнение: либо а R b, либо b R а, либо и то и другое.
Содержание
Введение…………………………………………………………………………..3
Глава I. Деревья, используемые в информатике………………………………5
Корневые деревья в информатике …………………………………..5
Двоичные деревья …………………………………………………….8
Виды двоичных деревьев……………………………………………..9
Глава II. Двоичные деревья в информатике…………………………………..10
Сортировка данных
Метод дерева сортировки ……………………………………10
Метод кучи……………………………………………………...16
Представление алгебраических выражений с помощью двоичных деревьев………………………………………………………………18
Заключение……………………………………………………………………...20
Библиографический список ………………………………………………….23
Работа содержит 1 файл
курсовая(дискретка).doc
— 162.50 Кб (Скачать)Также я рассмотрела два метода сортировки данных: по методу дерева сортировки и по методу кучи. В ходе рассмотрения были получены алгоритмы этих методов и показаны примеры их применения.
В теоретической части работы выделены три пункта:
-
корневые деревья в
- двоичные деревья;
- виды двоичных деревьев.
При анализе литературы по данному вопросу было выявлено, что не только двоичные деревья, но и корневые деревья имеют важное практическое применение в информатике. Например, корневые деревья используются при организации директории файлов, а так же выяснилось, что корневое дерево можно использовать и в обычной жизни человека. Примером этого является обыкновенное генеалогическое дерево человека.
Рассмотрела различные виды деревьев, которые также используются в информатике.
Деревья
важную роль играют при программировании.
Например, упорядоченные и
- представления выражения на языке программирования;
-
для представления блочной
-
для представления
-
структура вложенности
В дальнейшем данная тема может быть разработана по следующим направлениям:
- применение теории графов (деревьев) в школе;
-
показать применение деревьев в программирование.
Библиографический список
- Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979. – 143 с.
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
- Логинов Б. М. Введение в дискретную математику.- Калуга: Облиздат, 1998. – 423 с.
- Новиков, Ф.А. Дискретная математика для программистов/Ф.А. Новиков. – СПб.: Изд-во Питер, 2003. – 304 с.
- Оре, О. Теория графов/О. Оре. – М.: Наука, 1968. – 352 с.
- Редькин Н.П. дискретная математика. – СПб.: Лань, 2006. – 96 с.