- 1
- 2
- 3
- . . .
- последняя »
ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА
Федеральное государственное образовательное учреждение высшего профессионального образования
«Санкт-Петербургский государственный университет водных коммуникаций» КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ
ДИСКРЕТНАЯ МАТЕМАТИКА ТЕМА:
«ПРЕДСТАВЛЕНИЕ ДЕРЕВЬЕВ В ВИДЕ МАССИВА» Выполнил студент 2 курса
группы ИП-21:
Мальцев Валерий
Проверил:
Нырков Анатолий Павлович Санкт-Петербург
2009 г.
СодержаниеДеревья 8Терминология деревьев 9Бинарные деревья 10Представление бинарных деревьев 14Приложение 17Текст программы 18Список литературы 201)Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. 20
ДеревьяМассивы и связанные списки определяют коллекции объектов, доступ к которым осуществляется последовательно. Такие структуры данных называют линейными (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
- 3
- . . .
- последняя »
Похожие работы
Тема: Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево |
Предмет/Тип: Другое (Диплом) |
Тема: Представление чисел в виде суммы двух квадратов и ... |
Предмет/Тип: Математика (Реферат) |
Тема: Представление текстовой и графической информации в электронном виде |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (т)) |
Тема: Представление текстовой и графической информации в электронном виде |
Предмет/Тип: Другое (Курсовая работа (т)) |
Тема: Представление данных в виде диаграммы в MS Excel |
Предмет/Тип: Педагогика (Методичка) |
Интересная статья: Быстрое написание курсовой работы