Древовидная структура , древовидная диаграмма или древовидная модель — это способ представления иерархической природы структуры в графической форме. Она называется «древовидной структурой», потому что классическое представление напоминает дерево , хотя диаграмма обычно перевернута по сравнению с биологическим деревом, со «стволом» наверху и «листьями» внизу.
Древовидная структура концептуальна и проявляется в нескольких формах. Для обсуждения древовидных структур в конкретных областях см. Дерево (структура данных) для компьютерных наук; в той мере, в какой это относится к теории графов, см. дерево (теория графов) или дерево (теория множеств) . Другие связанные статьи перечислены ниже.
Элементы дерева называются « узлами ». Линии, соединяющие элементы, называются «ветвями». Узлы без потомков называются листовыми узлами , «конечными узлами» или «листьями».
Каждая конечная древовидная структура имеет элемент, у которого нет вышестоящего . Этот элемент называется «корнем» или корневым узлом . Корень является начальным узлом. Но обратное неверно: бесконечные древовидные структуры могут иметь или не иметь корневой узел.
Названия отношений между узлами моделируют терминологию родства семейных отношений. Нейтральные по половому признаку названия «родитель» и «ребенок» в значительной степени вытеснили старую терминологию «отец» и «сын». Термин «дядя» по-прежнему широко используется для других узлов на том же уровне, что и родитель, хотя иногда его заменяют нейтральными по половому признаку терминами, такими как «оммер». [1]
В этом примере "encyclopedia" является родителем "science" и "culture", его потомков. "Art" и "craft" являются братьями и сестрами, и потомками "culture", который является их родителем и, таким образом, одним из их предков. Также "encyclopedia", как корень дерева, является предком "science", "culture", "art" и "craft". Наконец, "science", "art" и "craft", как листья, не являются предками ни одного другого узла.
Древовидные структуры могут отображать все виды таксономических знаний, такие как генеалогические деревья , биологическое эволюционное дерево , эволюционное дерево языковой семьи , грамматическая структура языка (ключевым примером является S → NP VP, что означает, что предложение представляет собой именную группу и глагольную группу, каждая из которых, в свою очередь, имеет другие компоненты, которые имеют другие компоненты), способ логического упорядочения веб-страниц на веб-сайте, математические деревья целочисленных множеств и т. д.
В Оксфордском словаре английского языка зафиксировано использование терминов «древовидная структура» и «древовидная диаграмма» с 1965 года в работе Ноама Хомского « Аспекты теории синтаксиса» . [2]
В древовидной структуре существует один и только один путь из любой точки в любую другую точку.
В информатике широко используются древовидные структуры ( см. Дерево (структура данных) и телекоммуникации ).
Формальное определение см. в теории множеств , а обобщение, в котором потомки не обязательно являются преемниками, см. в префиксном порядке .
Существует множество способов визуального представления древовидных структур. Почти всегда они сводятся к вариациям или комбинациям нескольких основных стилей:
Классические диаграммы узлов-связей, которые соединяют узлы между собой отрезками линий:
Вложенные множества , которые используют включение или включение для демонстрации родительства; примерами служат TreeMaps , фрактальные карты и диаграммы Эйлера :
Многослойные «сосульковые» диаграммы, использующие выравнивание/смежность.
Списки или диаграммы, в которых используются отступы, иногда называемые « контурами » или « древовидными представлениями ».
Краткое описание:
Древовидная структура:
Соответствие вложенным скобкам впервые заметил сэр Артур Кейли :
((искусство, ремесло)культура, наука)энциклопедия
или
энциклопедия(культура(искусство, ремесло), наука)
Деревья также могут быть представлены радиально :
Определение некоторых основных стилей древовидных структур можно найти в:
