Алгоритм составления дерева по коду:

1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.

2. находим наименьшее натуральное число, которое не встречается в последовательности.

3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.

4. находим следующее число.

и т.д.

Рассмотрим применение данного алгоритма на примере.

Пример 1. Постройте дерево, которому соответствует код {1, 2, 2, 1, 1}

Решение.

1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.

2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).

3. Поскольку вершина (1) еще встречается в коде , то соединяем следующую висячую вершину (4) с вершиной из кода (2).

Повторяем для 5-2.

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

Далее 6 – 7. Код закончился, осталась 6. Соединяем ее с 1.

Дерево построено.

Пример 2. Построить дерево по коду Прюфера (3, 3, 4, 5, 4, 6).

Скачать решение, формат Word