Биноминальное дерево

Размещено на http://www.allbest.ru/

Введение

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

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

определение требований к программе;

разработка или выбор алгоритма решения поставленной задачи;

написание команд;

отладка;

тестирование.

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

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

алгоритм бинарный дерево программа

Задание: Заданная цель обусловила выделение следующих подзадач:

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

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

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

Создание бинарного дерева. Программа должна считывать числа от 0 до 9 и рекурсивно заполнять структуру дерева. Если пользователь вводит неверные значения - на экран будет выведено сообщение, предлагающее пользователю повторить попытку.

Удаление узла. Программа должна найти элемент в структуре и удалить его. При удалении элемента, которого не существует, будет выдано сообщение об ошибке.

Программа должна быть реализована используя конструкции языка С++ и среду программирования Microsoft Visual Studio.

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



2. Теоретические сведения

Данная программа писалась соответственно правилам создания бинарного дерева. Применялись основные возможности и операторы языка С++.

2.1 Бинарное дерево

Дерево -- одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Рис 2.1 Простой пример неупорядоченного дерева

2.1.1 Определения

Корневой узел -- самый верхний узел дерева.

Корень -- одна из вершин, по желанию наблюдателя.

Листовой узел или лист -- узел самого нижнего уровня дерева.

Листья дерева -- корни, из которых не выходит ни одной дуги.[1]

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

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

Дерево определения -- графическая диаграмма схемы базы данных.

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

2.1.2 Двоичное (бинарное) дерево

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

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

Двоичное дерево поиска (англ. binary search tree, BST) -- это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

Оба поддерева -- левое и правое, являются двоичными деревьями поиска.

У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.

У всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных узла X.

Очевидно, данные в каждом узле должны обладать ключами на которых определена операция сравнения меньше.

Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.



Рис 2.2 Пример двоичного дерева поиска

2.1.3 Рекурсивное определение

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

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

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

Рис 2.3 Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины n=(data, left, right) есть два ребёнка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.

2.1.4 Обход дерева

Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерева, а сам процесс называется обходом по дереву. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем -- правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева -- множество узлов с высотой N). Каждый уровень обходится слева направо.

2.2 Используемые операторы языка С/С++

2.2.1 Оператор if

Формат оператора:

Размещено на http://www.allbest.ru/

Выполнение оператора if начинается с вычисления выражения. Далее выполнение осуществляется по следующей схеме:

- если выражение истинно (т.е. отлично от 0), то выполняется оператор-1.

- если выражение ложно (т.е. равно 0),то выполняется оператор-2.

- если выражение ложно и отсутствует оператор-2 (в квадратные скобки заключена необязательная конструкция), то выполняется следующий за if оператор.

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

На месте оператор-1, так же как и на месте оператор-2 могут находиться сложные конструкции.

2.2.2 Оператор for

Оператор for - это наиболее общий способ организации цикла. Он имеет следующий формат:

Размещено на http://www.allbest.ru/

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

Схема выполнения оператора for:

1. Вычисляется выражение 1.

2. Вычисляется выражение 2.

3. Если значения выражения 2 отлично от нуля (истина), выполняется тело цикла, вычисляется выражение 3 и осуществляется переход к пункту 2, если выражение 2 равно нулю (ложь), то управление передается на оператор, следующий за оператором for.

Существенно то, что проверка условия всегда выполняется в начале цикла. Это значит, что тело цикла может ни разу не выполниться, если условие выполнения сразу будет ложным.

Некоторые варианты использования оператора for повышают его гибкость за счет возможности использования нескольких переменных, управляющих циклом.

2.2.3 Оператор return

Оператор return завершает выполнение функции, в которой он задан, и возвращает управление в вызывающую функцию, в точку, непосредственно следующую за вызовом. Функция main передает управление операционной системе. Формат оператора:

Размещено на http://www.allbest.ru/

Значение выражения, если оно задано, возвращается в вызывающую функцию в качестве значения вызываемой функции. Если выражение опущено, то возвращаемое значение не определено. Выражение может быть заключено в круглые скобки, хотя их наличие не обязательно. Если в какой-либо функции отсутствует оператор return, то передача управления в вызывающую функцию происходит после выполнения последнего оператора вызываемой функции. При этом возвращаемое значение не определено. Если функция не должна иметь возвращаемого значения, то ее нужно объявлять с типом void. Таким образом, использование оператора return необходимо либо для немедленного выхода из функции, либо для передачи возвращаемого значения. Также использовались функции из стандартной библиотеки, что облегчает выполнение задачи. 

3. Программная реализация

3.1 Описание алгоритма и структуры программы

В ходе выполнения программы:

Программа предлагает ввести количество элементов дерева, а затем сами элементы дерева.

Если пользователь введёт неверный символ, программа выдаст сообщение об ошибке, и будет осуществлён повторный ввод до тех пор, пока не будет введено правильное значение

Далее происходит сортировка дерева с последующим выводом его на экран

Программа предлагает ввести элемент, который должен быть удалён

Если пользователь введёт неверный символ, программа выдаст сообщение о том, что элемент не существует

Программа выводит на экран дерево с удаленным элементом

Пример работы программы:

Рисунок 3.1.1 - Начальное окно программы

Рисунок 3.1.2 - Ошибка при вводе неверных данных

Рисунок 3.1.3 - Полученное дерево

Рисунок 3.1.4 - Ошибка при вводе несуществующего элемента

Рисунок 3.1.5 - Вывод результата после удаления существующего элемента.



3.2 Описание разработанных функций

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

Функция создания элементов в дереве: elem * add_to_tree(int data, elem * el = NULL). Функция с помощью указателей elem * left, elem * right заполняет структуру elem. В ней el - динамическая память, используемая структурой.

Рис 3.2.1 Функция создания дерева

Функция поиска имеет прототип bool search(int data, elem * el). Является булевой, т.е. ищет элемент в структуре с помощью флагов true(правда) и false (ложь). Функция сравнивает не пустой элемент с корнем дерева и отправляет его в левое или же правое дочернее дерево. Затем таким же методом сравнения числе занимает своё место в дереве.



Рис 3.2.2 Функция поиска

Функция вывода имеет вид void print(elem * el). Если элемент не пустой, выводит последовательно упорядоченные элементы дерева.

Рис 3.2.3 Вывод дерева

Далее идёт проверка «на дурака» ввода с преобразованиями atoi и itoa. Данные записываются в переменные temp и temp2. Введенная строка данных 2 раза преобразуется и получаются переменные, которые сравниваются. Если после 2х преобразований эти переменные совпадают, то значит было введено число. Если же была введена буква, выведется соответствующее сообщение, предлагающее повторить попытку.



Рис 3.2.4 Проверка правильности ввода

Прототип функции удаления элементов выглядит следующим образом: elem * remove_element(int data, elem * el). Сначало программа ищет введенный элемент.

Если такого элемента не оказалось в дереве, выдаётся сообщение Element not found и выводится дерево без изменений.

Если такой элемент нашелся, он обнуляется и производится удаление всего дерево, корнем которого он является.

Рис 3.2.5 Удаление элемента



Рис 3.2.6 Главная функция программы:

Из неё осуществляется вызов функций, реализующих ввод количества элементов, ввод самих элементов, построение и вывод дерева, удаление элемента. После выполнения всех действий память освобождается возвратом в структуру нуля с помощью оператора return с последующей задержкой экрана, что реализуется благодаря оператору _getch.



4. Инструкция пользователя

Данная программа является курсовым проектом студента Харьковского национального университета радиоэлектроники группы КИ-10-4 Нечитайло Сергея.

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



Заключение

Была разработана программа для рекурсивного заполнения структуры числами, представляющая собой бинарное дерево. В программе используются алгоритмы работы со структурами и указателями, приёмы работы с текстовым выводом. Данные алгоритмы могут широко использоваться в различных задачах информатики. Например, структура данных двусвязный список, может быть построена с помощью записей и зануляемых ссылок, а именно, каждая запись будет предоставлять блок данных (узел, node), содержащий ссылки на «левый» и «правый» узлы, а также сами хранимые данные.

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



Перечень ссылок

1. Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы = Data Structures and Algorithms. -- М.: Вильямс, 2000. -- С. 384. -- ISBN 0-201-00023-7

2. Дональд Э. Кнут. Глава 2.3. Деревья // Искусство программирования = The Art of Computer Programming. -- 3-е изд. -- М.: Вильямс, 2000. -- Т. 2. Основные алгоритмы. -- 832 с. -- 7000 экз. -- ISBN 5-8459-0081-6

3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. -- 2-е изд. -- М.: «Вильямс», 2006. -- С. 1296. -- ISBN 5-8459-0857-4

4. Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. -- СПб.: ДиаСофтЮП, 2003. -- С. 672. -- ISBN 5-93772-081-4



Приложение А

Текст программы:

#include "stdafx.h"

#include <iostream>

#include <ctime>

#include <cstring>

#include <conio.h>

struct elem

{

int data;

elem * left;

elem * right;

};

elem * add_to_tree(int data, elem * el = NULL)

{

if(el == NULL)

{

el = new elem;

el->data = data;

el->left = el->right = NULL;

return el;

}

else

{

if(data < el->data)

el->left = add_to_tree(data, el->left);

else

el->right = add_to_tree(data, el->right);

return el;

}

}

bool search(int data, elem * el)

{if(el == NULL)

return false;

if(el->data == data)

return true;

return (data < el->data) ? search(data, el->left) : search(data, el->right);

}

void print(elem * el)

{

if(el != NULL)

{

print(el->left);

std::cout<<el->data<<"\n";

print(el->right);

}

}

void remove(elem * el)

{

if(el != NULL)

{

remove(el->left);

remove(el->right);

delete el;

}

}

int input()

{

char temp[100], temp2[100];

int num;

std::cin.getline(temp, 100);

num = atoi(temp);

itoa(num, temp2, 10);

if(strcmp(temp, temp2) != 0)

{

std::cout<<"Error!\nTry again\n";

return input();

}

return num;

}

elem * remove_element(int data, elem * el)

{

if (el==NULL)

std::cout<<"Element not found\n";

else

if(el->data == data)

{

remove(el);

return NULL;

}

else

if(data < el->data)

el->left = remove_element(data, el->left);

else

el->right = remove_element(data, el->right);

return el;

}

int main()

{

elem * tree = NULL;

int elems_num;

std::cout<<"\nVvedite kolichestvo elementov, a potom sami elementy!\n";

elems_num = input();

for(int i=0; i<elems_num; i++)

{

int t = input();

tree = add_to_tree(t, tree);

}

std::cout<<"\n";

print(tree);

std::cout<<"\nTest removing elements from tree\n";

std::cout<<"Chto udalyaem?\n";

int t = input();

tree = remove_element(t, tree);

print(tree);

remove(tree);

return 0;

getch ();

}

Размещено на Allbest.ru