Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Г
ЛАВА 
4. Д
ЕРЕВЬЯ
 
Предыдущая глава была посвящена рассмотрению рекурсивных алго-
ритмов. Однако рекурсивный подход может быть применен и для определе-
ния структур данных. Наиболее часто используемым видом таких структур 
являются деревья. Деревья имеют широкое применение при реализации 
трансляторов таблиц решений, при работе с арифметическими выражениями, 
при создании и ведении таблиц символов, где их используют для отображе-
ния структуры предложений, в системах связи для экономичного кодирова-
ния сообщений и во многих других случаях. 
Деревья наилучшим образом приспособлены для решения задач искус-
ственного интеллекта и синтаксического анализа. 
4.1. П
ОНЯТИЯ И ОПРЕДЕЛЕНИЯ
 
Древовидная структура (дерево) определяется следующим образом: де-
рево (tree) с базовым типом T — это 
− либо пустая структура; 
− либо узел типа T, с которым связано конечное число древовидных 
структур, называемых поддеревьями (subtree).
Если с узлом связаны только два поддерева, то дерево называется дво-
ичным (бинарным). В этой главе будут рассматриваться только двоичные 
деревья. 
Для описания деревьев используются термины, заимствованные из бо-
таники и генеалогии.
«Ботаническими» являются термины: 
− корень (root) – самый «верхний» узел дерева;
− ветвь (brunch) – цепочка связанных между собой узлов; 
− лист (leaf) – узел, не имеющий поддеревьев. 
Термины, заимствованные из генеалогии, описывают отношения: 
− родительским (parent) называется узел, который находится непо-
средственно над другим узлом;
− дочерним (child) называется узел, который находится непосредст-
венно под другим узлом;
− предки данного узла —  все узлы на пути от корня до данного уз-
ла; 
− потомки — все узлы, расположенные ниже данного. 
5 / 23

---

75 
Рис. 4.1. Представление дерева 
Специальные термины, связанные с программной реализацией деревьев 
и рядом специальных задач: 
− узел (node) — это точка, где может возникнуть ветвь; 
− внутренний узел (internal node) — узел, не являющийся ни лис-
том, ни корнем; 
− порядок узла  (node degree) — количество его дочерних узлов; 
− глубина (depth) узла — количество его предков плюс единица; 
− глубина (высота) дерева — максимальная глубина всех узлов; 
− длина пути к узлу — количество ветвей, которые нужно пройти, 
чтобы продвинуться от корня к данному узлу; 
− длина пути дерева — сумма длин путей всех его узлов, называе-
мая также длиной внутреннего пути.
− сестринские (братские) — узлы, у которых один и тот же роди-
тель.
Множество узлов, имеющих одинаковую глубину, образуют уровень 
дерева. Рисунок 4.1 демонстрирует общепринятое изображение дерева, как 
бы растущего вниз. 
6 / 23

---

76