Решение. 1. Будем последовательно приписывать вершинам данного ордерева двоичные строки, состоящие из нулей и единиц

Решение.

1. Будем последовательно приписывать вершинам данного ордерева двоичные строки, состоящие из нулей и единиц. Корню не припишем ничего, его левому потомку припишем 0, правому – 1 (рис 22).

Рис. 22.

2. Левому потомку 0 припишем индекс 00, а правому – 01, левому потомку 1 припишем индекс 10, а правому – 11 (см. рис 23).

Рис. 23.

3. Продолжим этот процесс, пока все висячие вершины не получат некоторый двоичный индекс (рис. 24).

Рис. 24.

4. Выпишем индексы висячих вершин слева направо.

{000, 001, 011, 101, 11}.

Это и есть префиксный код для заданного бинарного ордерева.

4. Восстановить бинарное ордерево по префиксному коду {00,010,011,101,11}.

Поскольку наибольшая длина двоичной строки в коде равна трём, то бинарное ордерево имеет не более трёх уровней.

Так как первые цифры строк равны либо 0, либо 1, то корень имеет два потомка (рис. 25).

	Рис. 25.

При этом каждый потомок корня имеет два потомка (рис.26).

Рис. 26.

Вершины 00 и 11 имеются в префиксном коде, поэтому уже являются висячими. Вершина 01 имеет два, а вершина 10 – одного потомка (рис.27(.

Поскольку отмечены все висячие вершины, составляющие префиксный код, то процесс завершён.

5. Найти код Прюфера заданного дерева (рис. 28).

Рис. 28

Дата добавления: 2014-11-20