Решение. Определим количество вершин искомого дерева

Определим количество вершин искомого дерева. В коде Прюфера 5 чисел, количество вершин на 2 больше, поэтому дерево имеет 7 вершин ().

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

список 1: {1, 2, 3, 4, 5,,6, 7}.

Слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является висячей. В нашем случае это вершина № 1. Рисуем ребро дерева, соединяющее эту вершину с вершиной, стоящей первой в коде Прюфера (то есть с вершиной № 3) (рис. 31).

Рис. 31  

Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины (например, подчёркиваем):

список 2: { 3, 3, 2, 5, 5},

список 1: {1, 2, 3, 4, 5, 6, 7}.

Снова слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является висячей. Теперь это вершина № 4. Рисуем ребро дерева, соединяющее эту вершину с вершиной, являющейся первой неотмеченной в коде Прюфера (то есть с вершиной № 3) (рис. 32).

Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины:

список 2: { 3, 3, 2, 5, 5},

список 1: {1, 2, 3, 4, 5, 6, 7}.

Ещё раз слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является «висячей». Это уже вершина № 3. Рисуем ребро дерева, соединяющее эту вершину с вершиной, являющейся первой неотмеченной в коде Прюфера (то есть с вершиной № 2) (рис.33).

Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины:

список 2: { 3, 3, 2, 5, 5},

список 1: {1, 2 , 3, 4, 5, 6, 7}.

Повторяем процесс до тех пор, пока не отметим все номера в списке 2. В результате получим (рис.34).

При этом в списке 1 останется две вершины (№ 5 и № 7). Поскольку одна из них (№ 5) есть в коде Прюфера, то вторая (№ 7) является висячей. Добавляем висячую вершину в рисунок (рис.35).

Искомое дерево построено.

7. Обойти бинарное ордерево тремя способами (рис.36).

Рис. 36  

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