По теме
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. Построить дерево по к ... Смотреть решение »