Примеры решения задач

Задача 1. Восстановить и нарисовать бинарное ордерево по префиксному коду {00,010,110,11}.

Решение. Наибольшая длина двоичной строки равна трем, следовательно, глубина ордерева также равна трем. Так как в префиксном коде указаны только висячие вершины, то по ним и восстанавливаем ордерево

0

1

00

11

01

110

010

Задача 2. Построить код Прюфера для дерева

Решение.

7

n=9

8

2

n-2=7

5

3

123456789

1

4

{4,7,8,8,4,7,4} – код Прюфера

9

6

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

Решение. Число символов в коде n-2=6, значит, у дерева n=8 вершин. Наименьшим из номеров, не входящих в код, является 3, значит, вершина 3 инцидентна вершине 1. Вычеркиваем 3 из списка вершин и просматриваем список дальше. Наименьшим из оставшихся и не входящих в код номеров является 5. Вершина 5 инцидентна вершине 1.

1 2 3 4 5 6 7 8 31.

1 2 3 4 5 6 7 8 51.

Продолжаем процесс:

1 2 3 4 5 6 7 8 74

(вершина 4 становится висячей).

1 2 3 4 5 6 7 8 41

(вершина 1 становится висячей).

1 2 3 4 5 6 7 8 16

(вершина 6 становится висячей).

1 2 3 4 5 6 7 8 62.

Изобразим дерево

8

2

6

3

1

4

5

7

Задачи для самостоятельного решения

Задача 1. Восстановить бинарное ордерево по префиксному коду: а) {001,010,011,1000,1010,110,1111}; б) {00,010,011,101,11}; в) {001,101,1101,111}.

Задача 2. Написать код Прюфера для данного дерева:

1

1

а) б)

4

5

6

2

8

7

2

4

6

9

8

11

3

7

10

9

3

5

Задача 3. Восстановить дерево по коду Прюфера: а) {2,2,4,4,3,6,2,3}; б) {3,1,2,2,1,4,4,3,3,5,1}; в) {2,3,6,6,2,7,2,6,3}.

§8. Обход дерева. Понятие списка. Деревья и списки

Часто необходимо обойти все вершины большого дерева не хаотически, а по определенному алгоритму. Для бинарных ориентированных деревьев существует три канонических способа обхода.

1. Прямой (КЛП – корень, лево, право). Сначала мы учитываем корень, затем левое поддерево и правое поддерево. Это правило выполняется для каждой вершины, начиная с корня.

2. Обратный (ЛКП – лево, корень, право). Сначала мы учитываем левое поддерево, затем корень и правое поддерево. Это правило выполняется для всех вершин, начиная с корня.

3. Концевой (ЛПК – лево, право, корень). Сначала мы учитываем левое поддерево, затем правое и корень.

Введем понятие атома. Атом – некоторый неделимый объект (буква, цифра и т.д.). Атомам соответствуют висячие вершины ордерева. Число вершин первого уровня является длиной списка. Причем, верно и обратное, что каждому дереву можно сопоставить список его висячих вершин.

Списком называется последовательность атомов и списков, заключенных в скобки и разделенных запятыми. Глубиной списка называется глубина дерева.

Примеры решения задач

Задача 1. Обойти тремя способами бинарное дерево

1

3

2

7

4

6

5

11

8

9

10

Решение. 1. Прямой (КЛП). 1 2 4 5 8 3 6 9 7 10 11.

2. Обратный (ЛКП) 4 2 8 5 1 6 9 3 1 0 7 1 1.

3. Концевой (ЛКП) 4 8 5 2 9 6 1 0 1 1 7 3 1.

Задача 2. Нарисовать дерево, соответствующее списку:

а) (а); б) (а,b,с); в) (а,(b,с), (е,(f,k))).

Решение.

а) б) с)

а

b

k

е

с

а

f