Двоичные деревья и их роль в информатике

Автор: Марья Иванова, 05 Октября 2010 в 16:39, курсовая работа

Описание работы

Впервые понятие «дерево» ввел физик Густав Кирхгофф в 1847 году. Будучи студентом Кенигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены, как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются не зависимыми, и Кирхгофф использовал деревья для получения независимого подмножества уравнений.
В последние десять лет компьютерная наука столкнулась с тем, что деревья обеспечивают удобные структуры для хранения и исправления определенных типов данных – так называемых иерархических баз данных.
Корневые деревья интенсивно используются в информатике. Деревья являются самым распространенным классом графов, применяемых в программировании. Наиболее важные применения деревьев этого типа связаны с представлением и сортировкой данных. Некоторые другие важные применения корневых деревьев в компьютерной науке связаны с представлением алгебраических выражений.
Обычным и важным действием при обработке данных является сортировка данных в соответствии с определенным критерием. Природа данных и цели их использования определяют особенности сортировки. Чаще всего приходится иметь дело с числовой или буквенной сортировкой. Предположим, что отношение представляет собой тотальный порядок, то есть такой порядок, при котором для любой пары элементов возможно сравнение: либо а R b, либо b R а, либо и то и другое.

Содержание

Введение…………………………………………………………………………..3
Глава I. Деревья, используемые в информатике………………………………5
Корневые деревья в информатике …………………………………..5
Двоичные деревья …………………………………………………….8
Виды двоичных деревьев……………………………………………..9
Глава II. Двоичные деревья в информатике…………………………………..10
Сортировка данных
Метод дерева сортировки ……………………………………10
Метод кучи……………………………………………………...16
Представление алгебраических выражений с помощью двоичных деревьев………………………………………………………………18
Заключение……………………………………………………………………...20
Библиографический список ………………………………………………….23

Скачать полностью (39.30 Кб) Сколько стоит заказать работу?
Работа содержит 1 файл

курсовая(дискретка).doc

— 162.50 Кб (Скачать)

    Также я рассмотрела два метода  сортировки данных: по методу дерева сортировки и по методу кучи. В ходе рассмотрения были получены алгоритмы этих методов и показаны примеры их применения.

    В теоретической части работы выделены три пункта:

    - корневые деревья в информатике;

    - двоичные деревья;

    - виды двоичных деревьев.

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

    Рассмотрела различные виды деревьев, которые также используются в информатике.

    Деревья важную роль играют при программировании. Например, упорядоченные и ориентированные  деревья используются для:

    - представления выражения на языке программирования;

    - для представления блочной структуры  программы и связанной с ней  структуры областей;

    - для представления иерархической  структуры вложенности данных  и операторов управления;

    - структура вложенности каталогов  и файлов в современных операционных системах.

    В дальнейшем данная тема может быть разработана по следующим направлениям:

    - применение теории графов (деревьев) в школе;

    - показать применение деревьев в программирование. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Библиографический список

    1. Березина Л.Ю.  Графы и их применение. – М.: Просвещение, 1979. – 143 с.
    2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
    3. Логинов Б. М. Введение в дискретную математику.- Калуга: Облиздат, 1998. – 423 с.
    4. Новиков, Ф.А. Дискретная математика для программистов/Ф.А. Новиков. – СПб.: Изд-во Питер, 2003. – 304 с.
    5. Оре, О. Теория графов/О. Оре. – М.: Наука, 1968. – 352 с.
    6. Редькин Н.П. дискретная математика. – СПб.: Лань, 2006. – 96 с.

Информация о работе Двоичные деревья и их роль в информатике