- Бинарное дерево
-
Двои́чное де́рево — структура данных, являющаяся программной реализацией двоичного дерева (графа). Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные привязанные к узлу, left, right — ссылки на узлы, являющиеся детьми данного узла. Узел left называется левым ребёнком (сыном), а узел right — правым.
Существует следующее рекурсивное определение двоичного дерева (см. БНФ):
<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .
То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной).
Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:
(m (e (c (a nil nil) nil ) (g nil (k nil nil) ) ) (s (p (o nil nil) (s nil nil) ) (y nil nil) ) )
Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.
Многие полезные структуры данных основаны на двоичном дереве:
Есть и другие способы представления двоичного дерева в памяти компьютера, в том числе не основанные на ссылочных типах данных. Например, в структуре данных Двоичная куча используется обыкновенный массив, и считается, что у элемента с индексом
K
левым и правым ребёнком являются элементы с индексами2K+1
и2K+2
соответственно (индексирование начинается с 0).
Wikimedia Foundation. 2010.