Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Деревья




Дерево есть конечное множество T узлов, такое, что:

1. имеется один специально обозначенный узел, называемый корнем дерева.

2. остальные узлы содержатся в m ³0 попарно непересекающихся множествах T1,T2,…Tm, каждое из которых является деревом.

Деревья T1,T2,…Tm называются поддеревьями данного корня. Строго говоря, приведенное определение относится к специальному случаю дерева, называемому корневым деревом. Деревья, в которых корень не выделен, называют висячими. Здесь рассматриваются исключительно корневые деревья.

Число поддеревьев узла называют его степенью. Узел нулевой степени называют листом. Уровень узла в дереве определяется следующим образом:

- корень имеет уровень 1

- корни поддеревьев узла имею уровень на 1 больший, чем уровень узла.

Высотой дерева называют наибольший уровень узла в нём.

Если в п.2 определения дерева имеет значение относительный порядок следования поддеревьев T1,T2,…Tm, то дерево называют упоря­доченным. Лес – это множество, быть может, пустое, состоящее из некоторого числа непересекающихся деревьев. Определение дерева рекурсивно и также рекурсивными являются большинство методов обработки деревьев.

Дерево можно изобразить различными способами. Изображения деревьев на рис. 20 эквивалентны.

Рис.20 Различные изображения деревьев

 

Примерами древовидной структуры являются генеалогические деревья, оглавления, формулы, классификации. На рис. 21 изображены деревья, изображающие формулу a-b*(c/d+e/f) и классификации товаров.

Рис. 21 Примеры деревьев

 

Когда говорят о деревьях, часто используют такие термины, как "отец", "сын", "брат", "предок", "потомок". Каждый узел является отцом корней своих поддеревьев. Последние являются братьями между собой и сыновьями своего отца. В упорядоченном дереве левый брат считается старшим. По аналогии можно ввести термины "дядя", "племянник" и другие. Термины "предок" и "потомок" употребляются для обозначения родства, простирающегося на несколько уровней дерева.




Поделиться с друзьями:


Дата добавления: 2014-12-08; Просмотров: 429; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.007 сек.