Задание на лабораторную работу: Создать двоичное дерево поиска, заполняя его числами из файла. Вывести на экран все его листья и неполные вершины, а также их количество.
Для начала немного теории для тех кто впервые работает с деревьями. Бинарное или двоичное дерево поиска представлено на рисунке снизу. Для данного рисунка приведем пример. Имеется набор чисел: 8, 3, 6, 10, 1, 14, 4, 7, 13. Необходимо построить бинарное дерево поиска. Объясняя простыми словами, вершиной дерева будет первое число, т.е. 8. Слева от него находятся меньшие числа, справа - бОльшие. Алгоритм построения бинарного дерева таков: вершина дерева 8, далее идет 3; 3 меньше чем 8, пускаем его влево; далее идет 6; 6 меньше чем 8, но больше чем 3; пускаем шестерку вправо от тройки; далее идет 10; 10 больше чем 8; пускаем ее вправо от восьмерки, и т.д.
Листьями в бинарном дереве называют вершины, имеющие степень 0. Говоря простым языком, это те вершины которые "болтаются", не имеют дальнейших связей. Для данного рисунка это вершины: 1, 4, 7 и 13.
Неполными вершинами в бинарном дереве называют вершины у которых только одна дальнейшая (идущая вниз) связь. Для данного рисунка это вершины: 10 и 14.
У бинарного дерева очень много интересных свойств, способов реализаций и прочего, но для данной работы вышеприведенной информации будет достаточно.
Теперь о программе.
Вначале 15 рандомных чисел от -99 до 99 программно генерируются и записываются в файл, а затем уже из файла считываются в дерево (требование задания). Имеются процедуры, котрые сами за себя говорят: addToTree (добавить число в дерево), printAllElem (вывести все элементы дерева), printLeaf (вывести листья), printNepVer (вывести неполные вершины)).
Приложение:
procedure addToTree(var tree: Ptree; x: Integer);
begin
if tree = nil then
begin
New(tree);
tree.num := x;
tree.left := nil;
tree.right := nil;
end
else
begin
if x < tree.num then
addToTree(tree^.left, x)
else
addToTree(tree^.right, x);
end;
end;
СОДЕРЖАНИЕ АРХИВА:
- Искомый dpr-файл
- Текстовый файл для чисел
Телеграм
-