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

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

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

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

Литература

[Кнут],

[Евстигнеев/85],

[Евстигнеев-Касьянов/94],

[Касьянов-Поттосин],

[Словарь]