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

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

Другое название — Двоичное дерево. Иногда под бинарным деревом просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. [math]\displaystyle{ m }[/math]-Арное дерево.

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

Литература

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

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

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

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

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