УП_САОД_2003

Спецификация двоичных деревьев

Как уже говорилось выше, двоичные (бинарные) деревья – это деревья со степенью не более двух.

По степени вершин двоичные деревья бывают:

строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).

В общем случае на k-м уровне двоичного дерева может быть до 2^k^-1 вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (то есть 2^k^-1 вершин на каждом k-м уровне), называется полным.

Рисунок 16. Двоичные деревья