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