Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

Лабораторная работа 3. БИНАРНЫЕ ДЕРЕВЬЯ

Задание

Опишите класс — дерево, необходимое для решения задачи, указанной в вашем варианте задания, и реализуйте его методы.

Продемонстрируйте работу основных методов работы с деревом:

построение, вывод, обход.

Составьте программу решения задачи, указанной в вашем варианте задания.

Варианты заданий

  • 1. Найти дубликаты в списке чисел с использованием дерева поиска.
  • 2. На основе операции обхода сверху вниз реализовать операцию, определяющую, подобны ли два бинарных дерева (два бинарных дерева подобны, если они оба пусты, либо их левые и правые поддеревья подобны).
  • 3. По бесскобочной постфиксной записи арифметического выражения с операндами, записанными в виде строк символов, построить дерево выражения и получить полноскобочное инфиксное выражение.
  • 4. Реализовать операцию определения уровня узла с заданным указателем в бинарном дереве, построить дерево с узлами — символами и определить минимальный и максимальный уровни листа.
  • 5. На основе процедуры обхода сверху вниз реализовать операцию поиска узла с заданным значением в дереве, не являющемся деревом поиска. Построить дерево минимальной высоты с элементами-символами. Используя операции Brother и Value, найти адрес брата узла с введенным с терминала значением и вывести его значение.
  • 6. Построить дерево поиска с элементами — строками. Используя операции Addr, Father и Value, найти узел, являющийся самым «молодым» общим предком двух заданных узлов, и вывести его значение.
  • 7. По постфиксной записи арифметического выражения с операндами-строками построить дерево выражения и получить инфиксную запись выражения, содержащую только необходимые скобки.
  • 8. Реализовать дерево поиска, содержащее элементы с одинаковыми ключами. Операция Addr возвращает адрес первого элемента с заданным ключом. Операция Delete исключает первый элемент с заданным ключом.
  • 9. Построить дерево поиска с элементами — вещественными числами. Определить количество элементов дерева на каждом уровне. Удалить элементы с заданными значениями.
  • 10. Построить дерево поиска с элементами — числами. С использованием операций Ас1с1г и Ое^еЬей найти узел с заданным значением и исключить его левое поддерево. Вывести число узлов в дереве до и после исключения.
  • 11. На основе просмотра текста построить дерево поиска, элементами которого являются символы, а ключами — количества вхождений этих символов в текст. Исключить из дерева символы с заданным числом повторений.
  • 12. Построить дерево поиска с элементами — строками. Исключить из дерева все узлы с заданными словами. При каждом исключении выводить текущее состояние дерева и сообщение о том, каким потомком является исключаемый узел: левым (операция 18Ьей) или правым (НЛ^М).
  • 13. На основе процедуры обхода дерева снизу вверх реализовать операцию поиска узла с заданным значением в дереве, не являющемся деревом поиска. Из двух последовательностей символов построить два бинарных дерева минимальной высоты. В первом дереве найти элемент с заданным значением и подключить второе дерево в качестве его левого поддерева, если оно пусто, или левого поддерева первого из его крайних левых потомков, имеющих пустое левое поддерево.
  • 14. На основе операции обхода сверху вниз реализовать операцию, определяющую, являются ли два бинарных дерева зеркально подобными (два бинарных дерева зеркально подобны, если они оба либо пусты, либо левое поддерево каждого дерева подобно правому дереву другого).
  • 15. По бесскобочной постфиксной записи арифметического выражения с операндами — строками построить дерево выражения и получить полноскобочное инфиксное выражение.
  • 16. По бесскобочной префиксной записи арифметического выражения с операндами — строками построить дерево выражения и получить выражение в инфиксной записи, содержащее только необходимые скобки.
  • 17. Реализовать дерево поиска, содержащее элементы с одинаковыми ключами. Операция АббгРцз! возвращает адрес первого элемента с заданным ключом. Операция Ое1е1еА11 исключает все элементы с заданным ключом.
  • 18. Построить бинарное дерево с элементами — символами. Вывести элементы дерева по уровням.
  • 19. Реализовать дерево выражения с операндами — числами и написать метод вычисления значения арифметического выражения. По бесскобочной префиксной записи построить дерево выражения и вычислить его значение.
  • 20. Реализовать операцию определения уровня узла с заданным указателем в дереве поиска, построить дерево с заданными числовыми значениями узлов и определить минимальный и максимальный уровни листа.
  • 21. На основе процедуры обхода дерева слева направо реализовать операцию поиска узла с заданным значением в дереве, не являющемся деревом поиска. Построить дерево минимальной высоты с числовыми значениями узлов. Используя необходимые операции, удалить из дерева поддерево, корнем которого является отец символа с заданным значением.
  • 22. Построить два дерева поиска для студентов двух групп с полученными на экзаменах оценками. Сформировать дерево для студентов, получивших отличные оценки, причем расположить их в дереве по алфавиту.
  • 23. Реализовать дерево поиска, содержащее элементы с одинаковыми ключами. Операция AddrLast возвращает адрес последнего элемента с заданным ключом. Операция DeleteFirst исключает первый элемент с заданным ключом.
  • 24. С использованием дерева поиска удалить из заданного текста дубликаты слов.
  • 25. Построить бинарное дерево с элементами — словами. Сформировать предложение из слов дерева, получающееся при обходе слева направо. Удалить поддерево, начинающееся с заданного слова.
  • 26. Построить дерево поиска с элементами — целыми числами. Удалить из дерева элементы с заданным значением, а все отрицательные элементы заменить нулями.
  • 27. Построить дерево поиска с заданными числовыми значениями. С использованием операций Addr и Father найти узел с заданным значением и удалить из дерева поиска отца этого узла.
  • 28. Построить дерево поиска с элементами — символами. Определить число повторяющихся символов в дереве и удалить дубликаты.
  • 29. Реализовать дерево поиска, содержащее элементы с одинаковыми ключами. Операция AddrLast возвращает адрес последнего элемента с заданным ключом. Операция DeleteAll исключает все элементы с заданным ключом.
  • 30. На основе просмотра текста построить дерево поиска, элементами которого являются символы, а ключами — количества вхождений этих символов в текст. Исключить из дерева символы с одинаковым числом повторений, используя строку для хранения последовательности узлов дерева (результатов обхода/

Пример выполнения задания

Построить дерево поиска с элементами — символами. Используя операции Addr, Father, Value и Delete, найти узел, являющийся отцом узла с заданным значением, вывести значение найденного узла и исключить его из дерева.

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

Класс — дерево поиска содержатся в модуле BinTrees.

//Лабораторная работа 3. Бинарные деревья.

// Выполнил Сергеев Андрей, группа 999.

// Работа с деревом поиска.

//Исходные данные - элементы дерева - в файле LW3Dat.txt //Результаты работы помещаются в файл LW3Res.txt program LW3;

{SAPPTYPE CONSOLE}

uses

SysUtils,

BinTrees in 'BinTrees.pas';

var

SearchTree : tSearchTree;//экземпляр дерева поиска fDat, fRes : Text; // файлы исходных данных и результатов

Item, Fathltem : pltem; //указатели на узел дерева и его отца v : tValue; //значение узла дерева

begin

Assign(fDat, 'LW3Dat.txt'); Reset(fDat);

Assign(fRes,'LW3Res.txt'); Rewrite(fRes);

//создание экземпляра SearchTree класса tSearchTree SearchTree := tSearchTree.Create;

// Построение дерева поиска SearchTree.Build(fDat);

WriteLn(fRes, 'Работа с деревом поиска');

WriteLn(fRes, 'Поиск и удаление отца заданного элемента дерева'); WriteLn(fRes, 'Построено дерево с числом узлов '.SearchTree.Size,':'); SearchTree.WriteTo(fRes); //вывод исходного дерева поиска

Write(fRes, 'Обход дерева слева направо:');

SearchTree.LeftRightRevision(fRes); //обход дерева слева направо Write(WinDos('AnB какого элемента нужно найти отца?'));

ReadLn(v);

WriteLn(fRes, 'Нужно найти отца для элемента v);

ltem:= SearchTree.Addr(v); //поиск узла со значением v

if ltem=nil

then WriteLn(fRes,'Элемента с ключом ',v,' в дереве нет.')

else begin

//Адрес отца узла со значением v Fathltem:= SearchTree. Father(ltem);

if Fathltem=nil then

// У заданного элемента нет отца WriteLn(fRes,'Заданный элемент не имеет отца.')

else begin

// У заданного элемента есть отец v:= SearchTree.Value(Fathltem);

WriteLn(fRes, 'Значение отца заданного элемента = ', v);

SearchTree.Delete(v); // исключение отца узла WriteLn(fRes,'Состояние дерева после исключения:'); SearchTree.WriteTo(fRes); //вывод дерева после исключения WriteLn(fRes, 'Обход дерева слева направо:'); SearchTree.LeftRightRevision(fRes); //обход дерева слева направо WriteLn(fRes,'Число узлов дерева:', SearchTree.Size); end; end;

SearchTree.Free;

Close(fDat); Close(fRes);

end.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы