Бинарное дерево

Бинарное дерево(Binary tree) — 1. Ордерево, растущее из корня, причем из каждой вершины исходит не более двух дуг, помеченных как правая или левая дуга. Другими словами, возможны следующие комбинации: выходят правая и левая дуги, выходит одна правая дуга, выходит одна левая дуга, нет выходящих дуг. На уровне $h$ бинарного дерева имеется максимум $2^{h}$ вершин. Поэтому бинарное дерево высотой $d$ имеет максимум $(2^{d+1} - 1)$ вершин, а дерево с $n$ вершинами имеет минимальную высоту $\log_{2} n$.

Другое название — Двоичное дерево. Иногда под бинарным деревом просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. $m$-Арное дерево.

2. Любая структура данных, используемая для представления бинарного дерева. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда бинарное дерево можно представить как указатель его корня.

Литература

• Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск.

• Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.