Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Деревья – динамические данные иерархической структуры произвольной конфигурации, состоящие из графов. Граф – это структура, состоящая из узлов (или вершин) и соединяющих их дуг. Графы бывают двух видов: ориентированные и неориентированные (если дуги не имеют стрелок).
Специального вида граф, в котором в каждую вершину может входить только одна стрелка, а выходить несколько, называется деревом (рисю 14.2).
Уровни:
0
а б
Рис. 14.2. Изображение дерева (а); структура, не являющаяся деревом (б)
Начальная вершина (в которую не входит стрелка) называется корнем. Вершины, из которых не выходят стрелки, – терминальные (листья) (помечены кружками). Структура, выходящая из одного узла – поддерево. Дерево, у которого из каждой вершины выходит не более двух стрелок, называется бинарным или двоичным деревом. Уровень – количество стрелок, которые нужно пройти, чтобы добраться от нулевого уровня к данной вершине.
В дереве может быть только один путь от корня к узлу; дерево не содержит петель и циклов, что следует из определения.
В виде деревьев можно изобразить отношения между субъектами из различных предметных областей.
П р и м е р ы деревьев
Факультет: 5 курсов, на каждом курсе – определенное число групп; в каждой группе – n человек.
Программа на ПК. Ее блоки составляют дерево, дуги которого означают вложенность структур.
Арифметическое выражение можно представить в виде деревьев, в узлах которых находятся операции, за исключением терминальных вершин. В них находятся переменные или числа (рис. 14.3).
Рис. 14.3. Формула в виде двоичного дерева
Для хранения и поиска информации наиболее часто применяют двоичные деревья.
Дата публикования: 2014-10-25; Прочитано: 301 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!