Задание
Разработать программу создания и обработки заданной структуры данных. Определить рекурсивные функции обходов дерева (в прямом, обратном и симметричном порядке).
Разработать пользовательский интерфейс.
Предусмотреть выполнение следующих обязательных опций:
1 - создать (ввести с клавиатуры и/или загрузить из файла);
2 - добавить (удалить) элемент;
3 - обход дерева;
4 - индивидуальное задание:
|
| Дерево двоичное
| Определение числа листьев
|
Анализ задания
Для решения данной задачи мы должны в первую очередь описать динамическую структуру данных «двоичное дерево» на основе указателей, написать стандартные операции работы с ним, а затем дополнить их операцией обхода дерева с подсчитыванием числа листьев на нём. Пользовательский интерфейс должен позволять производить с деревом стандартные операции, просматривать его (по крайней мере в самом общем виде) и определять число листьев.
Двои́чное де́рево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.
Разработка структуры программы
Рисунок 1. Структура программы.
Таблица 1. Спецификация программы.
| Имя модуля
| Имя вызывающего модуля
| Назначение
| Входные данные
| Выходные
данные
| Особенности
|
| main
| -
| Функция, инициализирующая программу
| -
| -
| -
|
| button1_Click
| main
| Выполнение выбранного пользователем действия
| comboBox1->SelectedIndex, textBox1->Text
| -
| Основная функция программы
|
| search
| button1_Click
| Поиск элемента
| tree *root, int name
| -
| -
|
| search_dubl
| button1_Click
| Поиск дубликатов
| tree *root
| -
| -
|
| obhod1
| button1_Click
| Рекурсивный обход 1 (Прямой обход)
| tree *root
| -
| -
|
| obhod2
| button1_Click
| Рекурсивный обход 2 (Обратный обход)
| tree *root
| -
| -
|
| obhod3
| button1_Click
| Рекурсивный обход 3 (Симметричный обход)
| tree *root
| -
| -
|
| obhod0
| button1_Click
| Рекурсивный обход 0 (Прямой обход) для подсчитывания числа листьев
| tree *root
| -
| Основана на функции obhod1
|
| delder
| button1_Click
| Удаление дерева
| tree *root
| tree *root
| -
|
| del
| button1_Click
| Удаление числа (элемента)
| tree *root, int name
| tree *root
| -
|
| descent
| del
| Спуск по дереву (для функции удаления)
| tree *p
| tree *y
| Вспомогательная функция для функции del
|
| add
| button1_Click
| Добавление числа
| tree *root, int n
| -
| -
|
| readfile
| button1_Click
| Считывание дерева из файла
| tree **root
| -
| -
|
| first
| button1_Click, readfile
| Создание первого элемента бинарного дерева
| int name
| tree *root
| Вспомогательная функция для функций button1_Click и readfile
|
