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

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

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

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

Решение.

n=9

n-2=7

123456789

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

Задача 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.

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

Y /gzeAAAACQEAAA8AAABkcnMvZG93bnJldi54bWxMj8FKxDAQhu+C7xBG8FLctF0VrU0XFfQgKNhd 8JptxrZrMylJtlt9ekc86PGf+fjnm3I120FM6EPvSEG2SEEgNc701CrYrB/OrkCEqMnowREq+MQA q+r4qNSFcQd6xamOreASCoVW0MU4FlKGpkOrw8KNSLx7d97qyNG30nh94HI7yDxNL6XVPfGFTo94 32HzUe+tgjq5exzoy09JNmW7t5enZPdsE6VOT+bbGxAR5/gHw48+q0PFTlu3JxPEwPkiv2ZUQX6e gWBgmadLENvfgaxK+f+D6hsAAP//AwBQSwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAA AAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQB AAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQCiyQxgCgIAAEAE AAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQCgWP4M3gAA AAkBAAAPAAAAAAAAAAAAAAAAAGQEAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAbwUA AAAA " strokecolor="black [3040]">