Базовые алгоритмы работы с бинарными деревьями. Построение дерева выражений. Практика 4

1.

Базовые алгоритмы работы с
бинарными деревьями. Построение
дерева выражений
Практика 4

2.

Определение минимальной суммы от корня к
листу
1. Рекурсивный подход
Здесь осуществляется полный обход дерева (посещение всех узлов)
2. Метод перебора с возратом.
Изменим стратегию нахождения минимальной суммы. Будем накапливать сумму в
глобальной переменной sum и всякий раз по достижении листа сравнивать ее с
глобальной переменной min.
Всякий раз, добавляя к сумме очередное значение, осуществляем перебор, и если
решение неполное, то продолжаем рекурсивные вызовы. После рекурсивных вызовов
мы осуществляем возврат суммы к предыдущему значению. В результате в каждой
точке в переменной sum хранится сумма элементов от корня к текущему узлу.
3. Метод перебора с возратом. Метод ветвей и границ.
Метод ветвей и границ является вариацией полного перебора, но производит отсев
подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

3.

Рекурсивный подход
int min_sum1(PNode Tree)
{
if (Tree == NULL) return 0;
else if ((Tree->left == NULL) && (Tree->right == NULL)) return Tree->key;
else if((Tree->left != NULL) && (Tree->right != NULL))
return Tree->key + min(min_sum1(Tree->left), min_sum1(Tree->right));
else if(Tree->left==NULL)
return Tree->key + min_sum1(Tree->right);
else if(Tree->right==NULL)
return Tree->key + min_sum1(Tree->left);
}

4.

Перебор с возратом
void min_sum2(PNode Tree)
{
if(Tree!=NULL)
{
sum2+=Tree->key;
if ((Tree->left==NULL) && (Tree->right==NULL) && (sum2<min2))
min2 = sum2;
min_sum2(Tree->left);
min_sum2(Tree->right);
sum2-=Tree->key;
}
}

5.

Метод перебора с возратом. Метод ветвей и
границ.
void min_sum3(PNode Tree)
{ if (Tree != NULL)
{ sum3 += Tree->key;
if (sum3<min3)
{
if ((Tree->left==NULL) && (Tree->right==NULL)) min3 = sum3;
else if(Tree->right==NULL) min_sum3(Tree->left);
else if (Tree->left==NULL) min_sum3(Tree->right);
else (Tree->left->key<Tree->right->key)? min_sum3(Tree->left) : min_sum3(Tree>right);
} }
}

6.

Задание на занятии
Задача 1. Создать дерево поиска, ключом служит целое число
(числа брать из текстового файла). Вывести на экран дерево боком и
со скобками. Вернуть пользователю адрес узла требуемого ключа
(значение вводит пользователь).
Задача 2. Создать дерево минимальной высоты, ключом служит
целое число (числа брать из текстового файла). Вывести на экран
узлы дерева по правилу прямого, обратного, концевого обходов.
Удалить из дерево узел с требуемым ключом (значение вводит
пользователь).
Задача 3. Построение дерева выражений (по файлу).
За каждое задание по 1 баллу в счет ДЗ.

7.

Домашнее задание: 1 балл
Задание по вариантам: 1 задача ( 4, 7, 11 варианты), 2 задача ( 3, 6, 10 варианты),
3 задача ( 2, 12, 15 варианты), 4 задача (1, 8, 13), 5 задача (5, 9, 14).
1. Дан указатель на корень непустого дерева и число K. Вывести количество
вершин дерева, значение которых кратно K.
2. Дан указатель на корень непустого дерева. Вывести сумму значений всех
четных вершин данного дерева.
3. Дан указатель на корень непустого дерева. Вывести количество вершин
дерева, являющихся левыми (правыми) дочерними вершинами (корень дерева
не учитывать).
4. Дан указатель на корень непустого дерева. Листом дерева называется его
вершина, не имеющая дочерних вершин. Вывести количество листьев для
данного дерева.
5. Дан указатель на корень непустого дерева. Листом дерева называется его
вершина, не имеющая дочерних вершин. Вывести сумму значений листьев для
данного дерева.