Древовидная структура - Tree structure

Древовидная структура, показывающая возможную иерархическую организацию энциклопедии
Первоначальная энциклопедия использовала древовидную диаграмму, чтобы показать, как были упорядочены ее предметы.

Структура дерева , древовидная схема или модель дерева является способом представления иерархической природы структуры в графической форме. Она названа «древовидной структурой», потому что классическое представление напоминает дерево , хотя диаграмма обычно перевернута по сравнению с биологическим деревом, со «стеблем» вверху и «листьями» внизу.

Древовидная структура концептуальна и представлена ​​в нескольких формах. Для обсуждения древовидных структур в определенных областях см. Дерево (структура данных) для информатики; насколько это относится к теории графов, см. дерево (теория графов) или дерево (теория множеств) . Другие статьи по теме перечислены ниже.

Терминология и свойства

Элементы дерева называются « узлами ». Линии, соединяющие элементы, называются «ветвями». Узлы без дочерних узлов называются листовыми узлами , «конечными узлами» или «листьями».

Каждая конечная древовидная структура имеет член, у которого нет старшего . Этот член называется «корневым» или корневым узлом . Корень - это начальный узел. Но обратное неверно: бесконечные древовидные структуры могут иметь или не иметь корневой узел.

Имена отношений между узлами моделируют родственную терминологию семейных отношений. Гендерно-нейтральные имена «родитель» и «ребенок» в значительной степени вытеснили старые термины «отец» и «сын». Термин «дядя» по-прежнему широко используется для других узлов на том же уровне, что и родительский, хотя иногда его заменяют нейтральными с гендерной точки зрения терминами, такими как «оммер».

  • «Родитель» узла - это узел на одну ступень выше в иерархии (т. Е. Ближе к корневому узлу) и лежащий на той же ветви.
  • «Родственные» («братские» или «сестринские») узлы совместно используют один и тот же родительский узел.
  • «Дяди» узла (иногда «оммеры») являются братьями и сестрами родительского узла.
  • Узел, подключенный ко всем узлам нижнего уровня, называется «предком». Подключенные узлы нижнего уровня являются «потомками» узла-предка.

В данном примере «энциклопедия» является родителем «науки» и «культуры», своих детей. «Искусство» и «ремесло» - это братья и сестры и дети «культуры», которая является их родителем и, следовательно, одним из их предков. Кроме того, «энциклопедия», как корень дерева, является родоначальником «науки», «культуры», «искусства» и «ремесла». Наконец, «наука», «искусство» и «ремесло», как листья, не являются предками ни одного другого узла.

Древовидные структуры могут отображать все виды таксономических знаний, такие как родословные , биологическое эволюционное дерево , эволюционное дерево языковой семьи , грамматическая структура языка (ключевой пример - S → NP VP, что означает, что предложение является существительным фраза и глагольная фраза, каждый из которых, в свою очередь, имеет другие компоненты, у которых есть другие компоненты), способ логической упорядоченности веб-страниц на веб-сайте, математические деревья целочисленных множеств и т. д.

В Оксфордский словарь английского языка записи использование как термины «структура дерева» и «дерево-схема» с 1965 по Ноам Хомский «s Аспекты теории синтаксиса .

В древовидной структуре существует один и только один путь из любой точки в любую другую точку.

Информатика широко использует древовидные структуры ( см. Дерево (структура данных) и телекоммуникации ).

Для формального определения см. Теорию множеств , а для обобщения, в котором дети не обязательно являются преемниками, см. Порядок префиксов .

Примеры древовидных структур

Древовидная карта, используемая для представления структуры каталогов как вложенного набора
информационная диаграмма в виде дерева, иллюстрирующая "эволюцию" термоэмиссионных трубок (разновидность вакуумных трубок) между 1883 и 1934 годами.

Представляя деревья

Есть много способов визуального представления древовидной структуры. Почти всегда они сводятся к вариациям или комбинациям нескольких основных стилей:

Классические схемы узловых ссылок

Классические схемы узловых связей, которые соединяют узлы вместе с отрезками линий:

энциклопедия
/
культура 		\
наука
/
искусство 		\
ремесло

Вложенные наборы

Вложенные наборы, которые используют вложение / включение для демонстрации отцовства, примеры включают TreeMaps и фрактальные карты :

Blank.png энциклопедия
Blank.png Blank.png
Blank.png культура
Blank.png Blank.png
художественный промысел
наука 

Многослойные схемы "сосульки"

Многослойные диаграммы «сосульки», использующие выравнивание / смежность.

энциклопедия
культура наука
Изобразительное искусство ремесло

Контуры и представления в виде дерева

Списки или диаграммы, использующие отступы, иногда называемые « контурами » или « древовидными представлениями ».

Схема:

энциклопедия
культура
Изобразительное искусство
ремесло
наука

Древовидный вид:

  • энциклопедия
    • культура
      • Изобразительное искусство
      • ремесло
    • наука

Вложенные круглые скобки

Смотрите также: формат Ньюика и язык Дика

Соответствие вложенным круглым скобкам впервые заметил сэр Артур Кэли :

((искусство, ремесло) культура, наука) энциклопедия
или
энциклопедия (культура (искусство, ремесло), наука)

Радиальные деревья

См. Также: Радиальное дерево

Деревья также могут быть изображены радиально :

искусство
      \ 		ремесло
/    
культура
|
энциклопедия
|
наука

Смотрите также

Виды деревьев
Статьи по Теме

использованная литература

  1. ^ «Глоссарий Ethereum» . GitHub . Проверено 17 апреля 2019 года .
  2. ^ "дерево" . Оксфордский словарь английского языка (Интернет-изд.). Издательство Оксфордского университета.  (Требуется подписка или членство в учреждении-участнике .)
  3. ^ "Что такое объектная модель документа?" . Домен архитектуры W3C . Проверено 5 декабря 2006 .

дальнейшее чтение

Идентификацию некоторых основных стилей древовидной структуры можно найти в:

внешние ссылки