Дерево (структура данных)
В компьютерных науках дерево — это широко используемый абстрактный тип данных , представляющий иерархическую древовидную структуру с набором связанных узлов . Каждый узел в дереве может быть связан со многими дочерними элементами (в зависимости от типа дерева), но должен быть связан ровно с одним родителем, за исключением корневого узла, у которого нет родителя. Эти ограничения означают отсутствие циклов или «циклов» (ни один узел не может быть своим собственным предком), а также то, что каждый потомок может рассматриваться как корневой узел своего собственного поддерева, что делает рекурсию полезной техникой обхода дерева . В отличие от линейных структур данных, многие деревья не могут быть представлены отношениями между соседними узлами на одной прямой.
Двоичные деревья являются широко используемым типом, который ограничивает количество дочерних элементов для каждого родителя ровно двумя. Когда порядок дочерних элементов указан, эта структура данных соответствует упорядоченному дереву в теории графов . Значение или указатель на другие данные могут быть связаны с каждым узлом в дереве, а иногда только с листовыми узлами , у которых нет потомков.
Абстрактный тип данных может быть представлен несколькими способами, включая список родителей с указателями на потомков, список потомков с указателями на родителей или список узлов и отдельный список отношений родитель-потомок (конкретный тип списка смежности ). Представления также могут быть более сложными, например, с использованием индексов или списков предков для повышения производительности.
Деревья, используемые в вычислениях, похожи, но могут отличаться от математических конструкций деревьев в теории графов , деревьев в теории множеств и деревьев в описательной теории множеств .
Документы JSON и YAML можно рассматривать как деревья, но обычно они представлены вложенными списками и словарями .
Узел — это структура, которая может содержать данные и соединения с другими узлами, иногда называемые ребрами или связями . Каждый узел в дереве имеет ноль или более дочерних узлов , которые находятся под ним в дереве (по соглашению деревья рисуются с потомками , идущими вниз). Узел, у которого есть дочерний узел, называется родительским узлом дочернего элемента (или вышестоящим ). Все узлы имеют ровно одного родителя, за исключением самого верхнего корневого узла , у которого их нет. У узла может быть много узлов-предков , таких как родитель родителя. Дочерние узлы с одним и тем же родителем являются родственными узлами .. Обычно братья и сестры имеют порядок, причем первый обычно рисуется слева. Некоторые определения позволяют дереву вообще не иметь узлов, и в этом случае оно называется пустым .
.svg)
