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

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

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

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

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

 

ТЕМА:

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

Выполнил студент 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. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. ............