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

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

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

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

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

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

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

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