Бинарные деревья

С точки зрения представления в памяти различают два типа деревьев: бинарные и сильноветвящиеся. В бинарном дереве из каждой вершины выходит не более двух дуг (рис. 7.7). В сильноветвящемся дереве количество дуг может быть произвольным. Вершины в дереве, имеющие степень ноль, называются листьями.

Рис. 7.7. Бинарное дерево.

Другим признаком структурной классификации бинарных деревьев является полнота и строгость бинарного дерева. Полное бинарное дерево на всех уровнях, меньше n имеют степень узла 2, а на уровне n степень равно 0 (рис. 7.8). Неполное бинарное дерево на уровнях, меньше n может иметь степень узла меньше 2. Строго бинарное дерево состоит только из узлов, имеющих степень два или ноль (рис. 7.9). Не строго бинарное дерево содержит узлы со степенью равной одному.

а). б).

Рис. 7.8. Неполное (а) и полное (б) бинарные деревья.

а). б).

Рис. 7.9. Строго (а) и не строго (б) бинарные деревья.

Дата добавления: 2014-01-07