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

Бинарное дерево(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. Любая структура данных, используемая для представления Б.д.. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда Б.д. можно представить как указатель его корня.}

Литература

[Кнут],

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

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

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

[Словарь]