Автор: Марья Иванова, 05 Октября 2010 в 16:39, курсовая работа
Впервые понятие «дерево» ввел физик Густав Кирхгофф в 1847 году. Будучи студентом Кенигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены, как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются не зависимыми, и Кирхгофф использовал деревья для получения независимого подмножества уравнений.
В последние десять лет компьютерная наука столкнулась с тем, что деревья обеспечивают удобные структуры для хранения и исправления определенных типов данных – так называемых иерархических баз данных.
Корневые деревья интенсивно используются в информатике. Деревья являются самым распространенным классом графов, применяемых в программировании. Наиболее важные применения деревьев этого типа связаны с представлением и сортировкой данных. Некоторые другие важные применения корневых деревьев в компьютерной науке связаны с представлением алгебраических выражений.
Обычным и важным действием при обработке данных является сортировка данных в соответствии с определенным критерием. Природа данных и цели их использования определяют особенности сортировки. Чаще всего приходится иметь дело с числовой или буквенной сортировкой. Предположим, что отношение представляет собой тотальный порядок, то есть такой порядок, при котором для любой пары элементов возможно сравнение: либо а R b, либо b R а, либо и то и другое.
Введение…………………………………………………………………………..3
Глава I. Деревья, используемые в информатике………………………………5
Корневые деревья в информатике …………………………………..5
Двоичные деревья …………………………………………………….8
Виды двоичных деревьев……………………………………………..9
Глава II. Двоичные деревья в информатике…………………………………..10
Сортировка данных
Метод дерева сортировки ……………………………………10
Метод кучи……………………………………………………...16
Представление алгебраических выражений с помощью двоичных деревьев………………………………………………………………18
Заключение……………………………………………………………………...20
Библиографический список ………………………………………………….23