Представление деревьев в виде бинарных.

Date: 2015-10-07; view: 455.

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

1. изображаем корень дерева;

2. по вертикали изображаем старшего сына этого корня;

3. по горизонтали вправо от этого узла представляем всех его братьев;

4. пп. 1, 2, 3 повторяем для всех его узлов.

		Таким образом, получаем, что вертикальные ребра изображают левые поддеревья, а горизонтальные – правые. Данный алгоритм можно распространить и для леса.

Теорема. Число бинарных деревьев с n вершинами можно выразить формулой: . Например, для n=3 имеем

Проиллюстрируем этот пример графически: