Question

Відновити дерево по коду Прюфера , даю 100 б
1, 5, 5, 9, 4, 3, 7, 11, 16,9,10,10,11,15

Answer 1

Для відновлення дерева за кодом Прюфера необхідно виконати наступні кроки:

1. Створити список степенів вершин, що складається з нулів.
2. Пройтися по коду Прюфера та знайти кількість повторень кожного числа. Додавати знайдену кількість до відповідних степенів вершин.
3. Знайти вершину з найменшою степенню та додати ребра до неї, щоб утворити дерево. Зменшити степені суміжних вершин на 1.
4. Повторити крок 3, поки не будуть додані всі ребра.

Отже, за кодом Прюфера 1, 5, 5, 9, 4, 3, 7, 11, 16, 9, 10, 10, 11, 15 будується наступне дерево:

1

/

5 5

/

9 4

/

7 3

/

11 16

/

10 9

/

10 15