---
title: Trees
localeTitle: деревья
---
# деревья

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

Бинарное дерево представляет собой нелинейную структуру данных, состоящую из узлов, где каждый узел имеет следующие 3 компонента:

**Элемент данных** : хранит любые данные в узле **Левый указатель** : указывает на поддеревье в левой части узла **Правильный указатель** : указывает на поддерево справа от узла Как следует из названия, элемент данных хранит любые данные в узле. Левый и правый указатели указывают на двоичные деревья с левой и правой стороны узла соответственно.

Если дерево пустое, оно представлено нулевым указателем.

## Терминология, используемая в деревьях:

**Корень** : Верхний узел в дереве.

**Ребенок** : Узел, напрямую подключенный к другому узлу при удалении от корня.

**Родитель** : Обратное понятие ребенка.

**Братья и сестры** : Группа узлов с одним и тем же родителем.

**Потомок** : Узлы достижимы путем повторного прохождения от родителя к дочернему.

**Предки** : Узел, доступный путем повторного прохождения от дочернего к родительскому.

**Ветвь** (внутренний узел): Узел дерева с дочерними узлами.

**Лист** (обычно называемый внешним узлом): Узел без детей.

**Степень** : Количество поддеревьев узла.

**Край** : Связь между одним узлом и другим.

**Путь** : Последовательность узлов и ребер, соединяющих узел с потомком.

**Уровень** : Уровень узла определяется 1 + (количество соединений между узлом и корнем).

**Высота дерева** : Высота дерева - это высота его корневого узла.

**Глубина** : Глубина узла - это количество ребер от корневого узла дерева до узла.

**Лес** : Лес представляет собой набор из n ≥ 0 непересекающихся деревьев.

### Некоторые популярные типы деревьев:

*   Двоичное дерево
*   Двоичное дерево поиска
*   Дерево AVL
*   Красный Черный Дерево
*   Splay Tree
*   Дерево Хаффмана

### Общее использование

*   Представление иерархических данных
*   Хранение данных таким образом, чтобы он был легко доступен для поиска
*   Представление отсортированных списков данных
*   Алгоритмы маршрутизации

### Код узла дерева

\`\` \`c\_cpp узел структуры { int данные; // Элемент данных struct node \* left; // Указатель на левый узел struct node \* right; // Указатель на правый узел };

\`\` \`

#### Дополнительная информация:

*   [Уроки урока CMU](http://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_1.htm)
*   [Википедия](https://en.wikipedia.org/wiki/Tree_(data_structure))