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

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

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

а) б)

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

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

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

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

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

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

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

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