2. Методика решения поставленой задачи и обоснование наравления разработки программного продукта

2.1 Обоснование выбранного языка программирования

Для реализации поставленной задачи был выбран язык программирования C#. Он является достаточно надежным языком по сравнению с C и C++. Так же он содержит огромное множество стандартных библиотек, которые значительно упрощают процесс написания программного кода. Его главными преимуществами являются лямбда-выражения и анонимные делегаты. С помощью лямбда-выражений и библиотеки LINQ легко реализовать на первый взгляд сложные задачи. Например, сортировка, замена, выборка из множества и тому подобное. C# унаследовал все лучшие качества таких языков, как C, C++, Delphi, Java.

Язык программирования C# базируется на 3 основных принципах: наследование, полиморфизм, инкапсуляция (как и любой другой ОО язык программирования). Он не поддерживает множественное наследование, но не запрещает реализовывать несколько интерфейсов в одном классе.

C# – элегантный, типобезопасный объектно-ориентированный язык, предназначенный для разработки разнообразных безопасных и мощных приложений, выполняемых в среде .NET Framework.

2.2 Методика решения поставленной задачи

Для решения поставленной задачи необходимо создать рекурсивный класс «Дерево», который будет содержать в себе все необходимые методы для работы с данными. Действия добавления, удаления, замены узла и визуализации дерева необходимо реализовать на отдельных формах для упорядочивания кода. Для передачи данных в объект класса «Дерево» из других форм удобнее всего будет воспользоваться событиями. Вывод данных и их сортировку проще всего реализовать через методы расширения LINQ и лямбда-выражения.

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

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

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

• посетить, перейти влево, перейти вправо;

• посетить, перейти вправо, перейти влево;

• перейти влево, посетить, перейти вправо;

• перейти вправо, посетить, перейти влево;

• перейти влево, перейти вправо, посетить;

• перейти вправо, перейти влево, посетить.

Из этих 6 вариаций 3 используются наиболее часто и имеют свои собственные стандартные названия: 1 – обход в прямом порядке, т.к. сперва посещается узел; 3 – симметричный обход, т.к. узлы обходятся в порядке сортировки их значений; и, наконец, 5 – обход в обратном порядке, потому что узел посещается после того, как совершены оба движения.

При обходе дерева в ширину чаще всего используется очередь. Суть этого способа проста:

1. В очередь добавляется первый элемент (корень).

2. Запускается цикл с условием выхода при количестве элементов очереди равным 0.

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

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

   3. Первый элемент очереди удаляется и цикл запускается заново.

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

– счетчик отрисованных узлов;

– переменная, отвечающая за «этаж» дерева.

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

– если у узла есть левое поддерево, то произвести для него этот же алгоритм сначала, изменив значение Y на +1, иначе отрисовать текущий узел по координате (X,Y), изменив значение X на +1;

– если у узла есть левое поддерево, то отрисовать текущий узел по координате (X,Y), изменив значение X на +1;

– если у узла есть правое поддерево, то проделать для него этот же алгоритм сначала.

У каждого узла должно быть свойство, отвечающее за положение узла (его координаты). И при отрисовке узлов, необходимо записыавть эти координаты в соответствующие свойства. Затем реализовать ещё один простой алгоритм:

– если у узла есть родитель, то провести от координат узла до координат родителя линию;

– если у узла есть левое поддерево, то проделать этот же алгоритм для левого поддерева;

– если у узла есть правое поддерево, то проделать этот же алгоритм для правого поддерева.

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

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

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