Реализация алгоритмов вычислительной математики с разработкой соответственного программного обеспечения для ЭВМ

Министерство образования и науки Украины

Государственное высшее учебное заведение

Приазовский государственный технический университет

Кафедра автоматизации и компьютеризации

КУРСОВОЙ ПРОЕКТ

По дисциплине: «Численные методы»

Тема: «Реализация алгоритмов вычислительной математики с разработкой соответственного программного обеспечения для ЭВМ»

Выполнил

Ст. гр И-16-МА

Вариант 16

Проверила

Кобыш Е.И.

Мариуполь 2016

Задание №1. Бинарное дерево.

Введение

Бинарное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.

Существует следующее рекурсивное определение двоичного дерева:

<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или терминальным элементом.

Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него.

Постановка задачи

        В исходном задании курсового проекта дано бинарное дерево следующего вида:

[pic 1]

Рис.1 – Полное двоичное дерево

Корнем дерева является узел А. Узлы B, C, D, E, F, G являются узлами ветвления. Узлы H, I, J, K, L, M, N, O – листья дерева. Корень и каждый узел ветвления имеют не больше двух наследников (правый и левый наследник), которым являются родителями. Листья не имеют наследников; корень не имеет родителя.

Исходное бинарное дерево имеет 4 уровня: 0, 1, 2, 3.

        Обозначим уровень символом , а количество вершин , тогда для бинарного дерева будет справедливо равенство , т. е. количество вершин на k-ом уровне не может иметь значение большее, чем степень двойки этого уровня.[pic 2][pic 3][pic 4]

Количество элементов для данного дерева:

[pic 5]

        Каждый элемент дерева имеет свой ключ, определяющий его место в дереве и связанное значение. Необходимо реализовать алгоритм вывода данных, содержащихся в этом дереве, уровень-за-уровнем, начиная с корня.

Математическая постановка задачи

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

[pic 6]

        Математически, задача сводится к сортировке методом дерева. В каждом узле дерева будут находиться связанные строковые данные, ключ узла (соответствующий порядковому номеру буквы в алфавите). Параметром сортировки строковых данных и сопоставления их с ключом будет являться длина введенной пользователем строки, получаемая функцией str.len().

Входные и выходные данные, их структура и представление в ЭВМ

        Пользователь вводит последовательно 15 строк символьной информации, после чего происходит считывание количества символов в строке. По этому критерию осуществляется сортировка методом двоичного дерева поиска. Осуществляется последовательный вывод имени ячейки (узла дерева A..O) и соответствующего ей поля символьной информации. В программе реализован алгоритм бинарного дерева поиска и бинарной кучи.

Блок-схема алгоритма решения задачи

[pic 7]

Рис.2 – Блок-схема работы двоичного дерева поиска

   Листинг программы

#include

#include