Деревья: основные понятия

Модуль "Деревья" • урок 1 из 11 • ~5 минут

Суть урока. До сих пор мы изучали линейные структуры (стек, очередь, списки). Дерево - это принципиально нелинейная, иерархическая структура данных, обладающая многозвенным разветвлением. В ней узлы связаны отношениями "отцы" и "дети", как в генеалогическом древе.

Деревья: корень наверху, внутренние узлы в середине и листья на концах ветвей — Название узла задает его место: корень наверху, листья на концах ветвей

Строение дерева

Элементы, входящие в дерево, называются узлами (или вершинами). В зависимости от своего расположения, узлы получают особые названия:

Корень - самый первый (верхний) узел дерева. У корня нет "отца".
Лист (концевой узел) - узел, у которого нет ни одного дочернего узла. Иными словами, ветка на нем заканчивается.
Внутренний узел - любой неконцевой узел, имеющий хотя бы одного потомка.

Каждое дерево обладает важными числовыми характеристиками:

Степень узла (арность) - количество дочерних поддеревьев у конкретного узла. У листьев арность всегда равна нулю.
Уровень узла - определяется рекурсивно. Корень находится на 1-м уровне, а каждый следующий шаг вниз увеличивает уровень на 1.
Глубина дерева - максимальное значение уровня среди всех его листьев.

Уровни дерева и его глубина: корень на уровне 1, узлы B и C на уровне 2, листья D и E на уровне 3 — Уровень считают от корня, глубина - это максимальный уровень листа

Генеалогия узлов

Для описания взаимного расположения узлов в дереве используется понятная терминология родственных связей:

Корень поддерева является "отцом" (предком) для всех корней вложенных поддеревьев.
Непосредственные потомки узла-отца называются его "сыновьями".
Узлы, имеющие одного и того же отца, приходятся друг другу "братьями".

Если порядок следования сыновей имеет значение (например, первый сын, второй, третий), то говорят, что узлы упорядочены слева направо. При этом используются термины: старший брат (самый левый) и младший брат (сосед справа). Такие структуры называют деревьями общего вида.

Позиционные деревья

В деревьях общего вида мы можем просто сказать: "у этого узла 3 сына". Но существует отдельный класс - позиционные деревья. В них для каждого узла строго зафиксировано количество возможных мест (позиций) для потомков, и каждая ветвь привязывается к конкретной позиции (даже если узел на этом месте отсутствует). Самый яркий пример позиционного дерева - двоичное (бинарное) дерево, где позиции строго определены как "левая" и "правая". В нем "левый сын" и "правый сын" - это принципиально разные сущности.

А как в Python? Встроенного типа "Дерево" в Python нет. Обычно дерево моделируют с помощью вложенных словарей dict (где ключи - это узлы, а значения - вложенные поддеревья), либо создавая свой класс узла со списком потомков: self.children = []. Так как списки в Python динамические, добавить любого по счету сына очень легко. В языке C из-за жесткой работы с памятью приходится придумывать более изощренные структуры, о которых мы поговорим в следующих уроках.

Коротко: главное

Дерево - это рекурсивная, иерархическая, нелинейная структура данных.
Дерево состоит из единственного корня (уровень 1), внутренних узлов и листьев.
Отношения между узлами описываются терминами родства: отцы, сыновья и братья.
В деревьях общего вида узел может иметь произвольное количество упорядоченных сыновей.
Глубина дерева равна максимальному уровню его листьев.

Проверьте себя

Как называется узел дерева, степень (арность) которого равна нулю?

Корень Лист Внутренний узел Младший брат

Как вам урок? Спасибо за отзыв!