Информатика и технология программирования


Задания к лабораторным работам - часть 2


Функция включения выбирает потомка минимальным количеством вершин в поддереве.



8. Вершина дерева содержит либо 4 целых значения, либо 2 указателя на потомков, причем концевые вершины содержат данные, а промежуточные - указатели на потомков. Естественная нумерация значений производится при обходе концевых вершин слева направо. Разработать функции получения и включения значения в дерево по логическому номеру.





9. Двоичное дерево представлено в массиве " естественным образом" : если вершина-предок имеет номер индекс n, то потомки - соответственно 2*n и 2*n+1. Нумерация начинается с n=1. Ячейка со значением 0 (или NULL) обозначает отсутствие вершины. Разработать функцию сортировки строк с использованием способа представления такого дерева в массиве указателей на строки.



10. Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений производится таким образом, что меньшие значения оказываются ближе к корню дерева (то есть все значения в поддеревьях больше самого большого значения у предка). Разработать функции включения и поиска данных в таком дереве. Если новое значение " проходит" через вершину, в которой находится большее, то оно замещает большее значение, а для последнего алгоритм включения. Функция включения выбирает потомка максимальным значением в поддереве.



11. Выражение, содержащее целые константы, арифметические операции и скобки, может быть представлено в виде двоичного дерева. Концевая вершина дерева должна содержать значение константы. Промежуточная - код операции и указатели на правый и левый операнды - вершины дерева. Функция получает строку, содержащую выражение, и строит по ней дерево. Другая функция производит вычисления по полученному дереву.



12. Вершина дерева содержит указатель на строку и динамический массив указателей на потомков. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция при включении строки создает вершину, наиболее близкую к корню.




Начало  Назад  Вперед



Книжный магазин