Тестирование и использование приложения

1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.

2.Выполните тестирование по рис.8.5. Разница между заданным и фактическим количеством узлов в дереве объясняется тем, что узлы для последующих равных чисел не создаются.

3.Выполните тестирование по рис.8.6. Здесь вначале используется автоматический режим формирования дерева, а затем – ручной.

4.Создать дерево, а затем – копию этого дерева. Деревья вывести в окно.

5.Создать два дерева, а затем одно дерево присвоить другому. Правильность действий подтвердить выводом в окно.

6.Реализовать вертикальный вывод дерева в окно.

7.Реализовать сохранение дерева в файле.

8.Написать обработчики соответствующих событий по п.4…п.7 и дополнить интерфейс.

9.Полученные результаты продемонстрировать преподавателю.

Рис.8.5 – формирование дерева в автоматическом режиме

Рис.8.6 - формирование дерева в автоматическом и ручном режимах

Контрольные вопросы

1.Расскажите о назначении и содержании класса TreeNode.

2.Как выделяется и инициализируется память для узла дерева?

3.Укажите в коде использование функций Left() и Right(). Почему они объявлены константными?

4.Как выполняются конструктор и деструктор класса TreeNode?

5.Расскажите о назначении и содержании класса BinSTree.

6.С какой целью класс BinSTree объявлен другом класса TreeNode?

7.Как выполняются конструктор и деструктор класса BinSTree?

8.Как осуществляется поиск узла по ключу?

9.Как выполняется функция Find?

10.Как добавляется узел в дерево?

11.Как создать дерево в автоматическом режиме?

12.Как создать дерево в ручном режиме?

13.Как выводится дерево в окно?

14.Поясните назначение и выполнение функции FindNode.

15.Почему нужен указатель на родителя удаляемого узла?

16.Как находят заменяющий узел, когда удаляемый узел имеет оба поддерева?

17.Как происходит замена удаляемого узла, если заменяющий узел не является его сыном?

18.При выполнении какого условия заменяют корень?

19.Расскажите о назначении и выполнении функций Delete, DeleteTree, ClearTree, CopyTree, Depth, CountLeaf.

20.Как сохранить дерево в файле?

21.Как вывести дерево из файла?

22.Как выполняется перегруженная операция присваивания?

23.Как создать новое дерево – копию другого дерева?

24.Как присвоить одно дерево другому?

25.Как реализовать вертикальный вывод дерева?

Задания

1.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести дерево и все его ветви на экран.

2.Массив из целых чисел представить в виде идеально сбалансированного бинарного дерева. Вывести дерево и слой с заданным ключом на экран.

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

4.Массив из чисел представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и ту половину дерева, где находится заданный ключ - с вершины, а другую половину - с корня.

5.Последовательность букв представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и все слои дерева, начиная с вершины, а затем - с корня.

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

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

8.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и слой с минимальным ключом.

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

10.Последовательность букв представить в виде идеально сбалансированного дерева. Вывести на экран дерево и ветви с гласными буквами.

11.Массив строк представить в виде упорядоченного бинарного дерева. Вывести дерево и слои со строками одинаковой длины на экран.

12.Массив строк представить в виде идеально сбалансированного дерева. Вывести дерево, слой и ветвь со строкой максимальной длины на экран.

13.Два бинарных дерева зеркально подобны, если либо оба они пусты, либо оба непусты, и при этом левое поддерево одного из них подобно правому поддереву другого и наоборот. Определить, являются ли два дерева зеркально подобными.

14.Два бинарных дерева подобны, если либо оба они пусты, либо оба непусты, и при этом их левые и правые поддеревья подобны. Определить, являются ли два дерева подобными.

15.Составить программу, которая читает произвольный C-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающих в первых N символах, но различающихся где-либо дальше. При решении задачи использовать дерево с узлами вида: struct NODE{char* word; int k; NODE* left; NODE* right;};. (Слова внутри символьных строк и комментариев не рассматривать.)

16.Формулу вида <формула>::=<цифра>|(<формула><знак><формула>) <знак>::= + | - | * <цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 можно представить в виде бинарного дерева по следующим правилам: а)формула из одной цифры представляется деревом из одной вершины с этой цифрой; б)формула вида f1# f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул f1,f2 в виде бинарных деревьев. Например, формуле 5*(3+8) соответствует дерево

*

/ \

5 +

/ \

3 8

Требуется: а)построить дерево по формуле указанного выше вида; б)вычислить как целое число значение дерева-формулы; в)по заданному дереву распечатать соответствующую формулу.

17.Составить программу, формирующую “перекрестные списки”, т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных: struct LIST //список номеров строк для данного слова

{ int num; struct LIST* p; }

struct NODE //узел дерева с информацией об очередном слове

{ char* word; struct LIST*lines; struct NODE*left; struct NODE*right;}.

18.Распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождений в текст). При решении задачи использовать дерево следующей структуры:

struct NODE

{char* word; int k; struct NODE* left; struct NODE* right;}.

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

20.В упорядоченном бинарном дереве удалить все листья.

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

22.Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде бинарного дерева; б)добавление данных о книгах, вновь поступающих в библиотеку; в)удаление данных о списываемых книгах; г)по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.

23.Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать: а)хранение всех заявок в виде бинарного дерева; б)добавление и удаление заявок; в) по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением; г)вывод всех заявок.

24.Англо-русский словарь построен как бинарное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначально дерево формируется согласно английскому алфавиту. В процессе эксплуатации словаря при каждом обращении к компоненте в счетчик обращений добавляется единица. Составить программу, которая: 1)обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений; 2)формирует новое представление словаря в виде бинарного дерева по следующему алгоритму: а)в старом словаре находится компонента с наибольшим значением счетчика обращений, б)найденная компонента заносится в новый словарь и удаляется из старого, в)переход к п. ‘а)’ до исчерпания исходного словаря; 3)производит вывод исходного и нового словарей. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

25.На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как бинарное дерево. Составить программу, которая: 1)обеспечивает начальное формирование картотеки в виде бинарного дерева; 2)производит вывод всей картотеки; 3)вводит номер телефона и время разговора; 4)выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

26.Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде бинарного дерева. Составить программу, которая: 1)обеспечивает первоначальный ввод данных в информационную систему и формирование бинарного дерева; 2)производит вывод всего дерева; 3)вводит номер поезда и выводит все данные об этом поезде; 4)вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

27.Бинарное упорядоченное дерево стереть слой за слоем, начиная с максимально дальней вершины.

28.В идеально сбалансированном бинарном дереве удалить узел с заданным ключом.

29.По исходному бинарному дереву построить подобное дерево.

30.По исходному бинарному дереву построить зеркально подобное дерево.