Решение. Запишем список всех вершин в порядке возрастания номеров:

Запишем список всех вершин в порядке возрастания номеров:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Рассматривая список слева направо, находим первую висячую вершину. В нашем случае это вершина № 3. Определяем номер смежной с ней вершины (№ 2) и записываем его в новый список. При этом номер висячей вершины «удаляем» из первоначального списка:

список 2: {2, …},

список 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},

а саму вершину из дерева (рис. 29).

Рис. 29  

Возвращаемся к началу списка 1 и повторяем процесс: находим первую висячую вершину (№ 4), определяем номер смежной с ней вершины (№ 2) и записываем его в новый список. При этом номер висячей вершины «удаляем» из первоначального списка:

список 2: {2, 2…},

список 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},

а саму вершину из дерева (рис. 30).

Рис. 30  

Повторяем процесс до тех пор, пока в списке 2 не окажется числа, где - количество вершин в исходном дереве (в нашем случае ).

Окончательно, получаем список 2: {2, 2, 1, 1, 1, 6, 7, 7, 6}. Это и есть код Прюфера для данного дерева.

6. Восстановить дерево по коду Прюфера: {3, 3, 2, 5, 5}.

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