Бинарное дерево. Написать программу, которая строит Т1 – копию заданного дерева Т - Free Pascal
Формулировка задачи:
Написать программу, которая строит Т1 – копию заданного дерева Т.
Решение задачи: «Бинарное дерево. Написать программу, которая строит Т1 – копию заданного дерева Т»
textual
Листинг программы
{$mode objfpc}
type
ptree = ^ttree;
ttree =
record
info : integer;
l, r : ptree;
end;
function MakeTree(s : integer; left_tree, right_tree : ptree) : ptree;
begin
new(result);
result^.info := s;
result^.l := left_tree;
result^.r := right_tree;
end;
function CopyTree(root : ptree) : ptree; // вот функция копирования
begin
if root = nil then result := nil
else
begin
new(result);
result^.info := root^.info;
result^.l := CopyTree(root^.l);
result^.r := CopyTree(root^.r);
end;
end;
procedure Symm(root : ptree; level : integer);
begin
if root = nil then exit;
Symm(root^.r, level + 1);
writeln(root^.info:3*level);
Symm(root^.l, level + 1);
end;
var
root : ptree;
t : ptree;
begin
// Это будет заданное дерево
root :=
MakeTree(20,
MakeTree(7,
MakeTree(4, nil, nil),
MakeTree(16, nil,
MakeTree(18, nil, nil))),
MakeTree(38,
MakeTree(37, nil, nil),
MakeTree(43, nil, nil)));
symm(root, 0); // выводим оригинал
writeln;
t := CopyTree(root); // Копируем его в новое дерево
symm(t, 0); // И сравниваем полученное дерево с оригиналом
writeln;
readln;
// не забудь удалить деревья
end.
Объяснение кода листинга программы
- Программа создает тип данных
ptree, который представляет собой узел бинарного дерева. - Функция
MakeTreeсоздает новый узел с заданным значением и двумя пустыми поддеревьями. - Функция
CopyTreeрекурсивно копирует заданное дерево, создавая новое дерево с теми же значениями и структурой. - Процедура
Symmрекурсивно выводит уровень дерева в отступе, начиная с заданного узла. - В основной части программы создается исходное дерево с помощью функции
MakeTree. - Процедура
Symmвызывается для вывода исходного дерева. - Создается копия исходного дерева с помощью функции
CopyTree. - Процедура
Symmвызывается для вывода скопированного дерева. - В конце программы требуется ввести данные, чтобы завершить работу программы.
- Все деревья освобождаются, когда они больше не нужны, чтобы избежать утечки памяти.