1. Главная
  2. Библиотека
  3. Информатика
  4. Восстановите дерево, если его код Прюфера (7, 7, 3, 2, 3, 4).

Восстановите дерево, если его код Прюфера (7, 7, 3, 2, 3, 4).

«Восстановите дерево, если его код Прюфера (7, 7, 3, 2, 3, 4).»
  • Информатика

Условие:

Восстановите дерево, если его код Прюфера (7, 7, 3, 2, 3, 4).

Решение:

1. Длина кода Прюфера равна 6, поэтому в дереве 8 вершин. Среди вершин 1, 2, . . . , 8 в коде не встречаются [1, 5, 6, 8], поэтому это листья, причем наименьший номер у 1, то есть эта вершина была удалена на первом шаге, поэтому она соединена с 7. 2. Теперь код выглядит как (7, 3, 2, 3, 4), не удалены вершины [2, 3, 4, 5, 6, 7, 8], а листьями будут [5, 6, 8]. Наименьший номер у 5, поэтому подвешиваем ее к 7. 3. Код равен (3, 2, 3, 4), остались вершины [2, 3, 4, 6, 7, 8], листья [6, 7, 8], соединяем 6 и 3. 4. Код равен (2, 3, 4), остались вершины [2, 3, 4, 7, 8], листья [7, 8], с...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет