Создание двоичного упорядоченного дерева

 

Оглавление

. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

2. Теоретический материал по используемым динамическими структурам данных и средствам разработки приложений с графическим интерфейсом на С#

2.1 Введение

.2 Рисование в форме

.3 Класс Graphics

.4 Кисти и краски

.5 Организация интерфейса

.6 Схема обработки исключений в C#

. АЛГОРИТМ ПРОГРАММЫ В ВИДЕ ПСЕВДОКОДА

.1 Tree.cs

.2 Form1.cs

. РЕЗУЛЬТАТЫ ВЫПОЛНЕНИЯ ПРОГРАММЫ

. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

. ПРИЛОЖЕНИЯ

1. Задание на выполнение работы

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

2. Теоретический материал по используемым динамическими структурам данных и средствам разработки приложений с графическим интерфейсом на С#

.1 Введение

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

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

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

Начальный узел называется корнем.

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

Рис.1

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

Рис.2

В деревьях бинарного поиска данные узлов можно сравнивать между собой, используя знаки сравнения «<», «>», «=»;

Для любого узла n должны выполняться следующие правила:

·Данные узла n не могут быть меньше данных с любого узла левого поддерева n (хотя допустимым является равенство с одним из таких узлов);

·Данные узла n строго меньше данных любого из узлов правого поддерева.

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

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

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

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

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

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

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

2.2 Рисование в форме

Графика необходима при организации пользовательского интерфейса. Образы информативнее текста. Framework .Net реализует расширенный графический интерфейс GDI+, обладающий широким набором возможностей. Но для рисования в формах достаточно иметь три объекта - перо, кисть и, хочется сказать, бумагу, но третий нужный объект - это объект класса Graphics, методы которого позволяют в формах заниматься графикой - рисовать и раскрашивать.

2.3 Класс Graphics

Класс Graphics - это основной класс, необходимый для рисования. Класс Graphics, так же, как и другие классы для перьев и кистей, находятся в пространстве имен Drawing, хотя классы некоторых кистей вложены в подпространство Drawing2D.

Объекты этого класса зависят от контекста устройства, (графика не обязательно отображается на дисплее компьютера, она может выводиться на принтер), поэтому создание объектов класса Graphics выполняется не традиционным способом - без вызова конструктора класса. Создаются объекты специальными методами разных классов. Например, метод CreateGraphics класса Control - наследника класса Form - возвращает объект, ассоциированный с выводом графики на форму.

При рисовании в формах можно объявить в форме поле, описывающее объект класса Graphics:graph;

а в конструкторе формы произвести связывание с реальным объектом:= CreateGraphics();

2.3.1 Методы класса Graphics

У класса Graphics большое число методов и свойств. Группа статических методов класса позволяет создать объект этого класса, задавая например описатель (handle) контекста устройства.

Для рисования наиболее важны три группы методов. К первой относится перегруженный метод DrawString, позволяющий выводить тексты в графическом режиме. Вторую группу составляют методы Draw - DrawEllipse, DrawLine, DrawArc и другие, позволяющие цветным пером (объектом класса Pen) рисовать геометрические фигуры: линии, различные кривые, прямоугольники, многоугольники, эллипсы и прочее. К третьей группе относятся методы Fill - FillEllipse, FillPie, FillRectangle и другие, позволяющие нарисовать и закрасить фигуру кистью. Кисти (объекты классов, производных от Brush), могут быть разные - сплошные, узорные, градиентные.

бинарный пользовательский интерфейс графический

2.3.2 Класс Pen

Методам группы Draw класса Graphics, рисующим контур фигуры, нужно передать перо - объект класса Pen. В конструкторе этого класса можно задать цвет пера и его толщину (чаще говорят ширину пера). Цвет задается объектом класса (структурой) Color. Для выбора подходящего цвета можно использовать упоминавшееся выше диалоговое окно Color либо одно из многочисленных статических свойств класса Color, возвращающее требуемый цвет. Возможно и непосредственное задание элементов структуры в виде комбинации RGB - трех цветов - красного, зеленого и голубого. Вместо создания нового пера с помощью конструктора можно использовать специальный класс предопределенных системных перьев.

2.3.3 Класс Brush

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

§SolidBrush - для сплошной закраски области заданным цветом;

§TextureBrush - для закраски области заданной картинкой (image);

§HatchBrush - для закраски области предопределенным узором;

§LinearGradientBrush - для сплошной закраски с переходом от одного цвета к другому, где изменение оттенков задается линейным градиентом;

§PathGradientBrush - для сплошной закраски с переходом от одного цвета к другому, где изменение оттенков задается более сложным путем.

§Первые два класса кистей находятся в пространстве имен System.Drawing, остальные - в System.Drawing.Drawing2D.

У каждого из этих классов свои конструкторы. В примере, обсуждаемом далее, рассмотрим создание кистей трех разных классов, там и поговорим о конструкторах классов.

Говоря о рисовании, нельзя не упомянуть о событии Paint. Оно возникает всякий раз, когда область, в которой происходило рисование, повреждена. Причины этого могут быть разные - пользователь свернул форму, изменил ее размеры, произошло перекрытие другой формой, был вызван метод Invalidate - во всех этих случаях требуется перерисовать область. Тогда-то и возникает событие Paint, в задачу его обработчика входит перерисовка поврежденной области.

2.4 Кисти и краски

ØДеление (размер таблицы hashTableSize - простое число). Этот метод использован в последнем примере. Хеширующее значение hashValue, изменяющееся от 0 до (hashTableSize - 1), равно остатку от деления ключа на размер хеш-таблицы.Для успеха этого метода очень важен выбор подходящего значения hashTableSize. Если, например, hashTableSize равняется двум, то для четных ключей хеш-значения будут четными, для нечетных - нечетными. Ясно, что это нежелательно - ведь если все ключи окажутся четными, они попадут в один элемент таблицы. Аналогично, если все ключи окажутся четными, то hashTableSize, равное степени двух, попросту возьмет часть битов Key в качестве индекса. Чтобы получить более случайное распределение ключей, в качестве hashTableSize нужно брать простое число, не слишком близкое к степени двух.

ØМультипликативный метод (размер таблицы hashTableSize есть степень 2n). Значение key умножается на константу, затем от результата берется n бит. В качестве такой константы Кнут рекомендует золотое сечение (sqrt(5) - 1)/2 = 0.6180339887499. Пусть, например, мы работаем с таблицей изhashTableSize=32(25) элементов, хэширование производится байтами(8 бит, unsigned char). Тогда необходимый множитель: 28*sqrt(5) - 1)/2 = 158.

ØДалее, умножая 8-битовый ключ на 158, будем получать некоторое 16-битное число. Для таблицы длиной 25 в качестве хеширующего значения берем 5 старших битов младшего слова, содержащего такое произведение.

ØАддитивный метод для строк переменной длины (размер таблицы равен 256). Для строк переменной длины вполне разумные результаты дает сложение по модулю 256. В этом случае результат hashValue заключен между 0 и 255.

ØИсключающее ИЛИ для строк переменной длины (размер таблицы равен 256). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX). Метод, как легко догадаться, заключается в том, что к элементам строки последовательно применяется операция "исключающее или". В нижеследующем алгоритме добавляется случайная компонента, чтобы еще улучшить результат.

ØИсключающее ИЛИ для строк переменной длины (размер таблицы <= 65536). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до 65536. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 16-битовое.

2.5 Организация интерфейса

Для добавления выделенных пользователем элементов к другому списку используется коллекция SelectedItems и метод Add, поочередно добавляющий элементы коллекции. Метод AddRange для добавления всей коллекции не всегда подходит, поскольку нет автоматического преобразования между коллекциями ObjectCollection и SelectedObjectCollection.

2.6 Схема обработки исключений в C#

Язык C# наследовал схему исключений языка С++, внеся в нее свои коррективы. Рассмотрим схему подробнее и начнем с синтаксиса конструкции try-catch-finally:

try {…}(T1 e1) {…}

…(Tk ek) {…} {…}

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

Параллельная работа обработчиков исключений

Обработчику исключения - catch-блоку, захватившему исключение, - передается текущее исключение. Анализируя свойства этого объекта, обработчик может понять причину, приведшую к возникновению исключительной ситуации, попытаться ее исправить и в случае успеха продолжить вычисления. В принятой C# схеме без возобновления обработчик исключения не возвращает управление try-блоку, а сам пытается решить проблемы. После завершения catch-блока выполняются операторы текущего метода, следующие за конструкцией try-catch-finally.

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

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

2.6.1 Класс Exception

Основными свойствами класса являются:

§Message - строка, задающая причину возникновения исключения. Значение этого свойства устанавливается при вызове конструктора класса, когда создается объект, задающий исключение;

§HelpLink - ссылка (URL) на файл, содержащий подробную справку о возможной причине возникновения исключительной ситуации и способах ее устранения;

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

§Source - имя приложения, ставшего причиной исключения;

§StackTrace - цепочка вызовов - методы, хранящиеся в стеке вызовов в момент возникновения исключения;

§TargetSite - метод, выбросивший исключение.

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

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

В заключение темы исключений хочу еще раз подчеркнуть, что корректное применение механизма исключений должно поддерживаться целенаправленными усилиями программиста. Следует помнить о двух важных правилах:

Øобработка исключений должна быть направлена не столько на уведомление о возникновении ошибки, сколько на корректировку возникшей ситуации;

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

3. Алгоритм программы в виде псевдокода

.1 Tree.cs

Класс VerhinaR = 20

Функция Verhina(n).n = n= right = null= Color.White

Конец функции Verhina(n)

Функция DobavimVershinu(n)

Если (n == this.n), то

Вывод окна("Такая вершина уже есть!",

"Ошибка", MessageBoxButtons.OK,.Error)

Вернуть

Все - Если

Если (n < this.n), то

Если (left == null), то= новый Verhina(n)

Иначе.DobavimVershinu(n)

Все - Если

Иначе

Если (right == null), то= новый Verhina(n)

Если.DobavimVershinu(n)

Все - Иначе

Конец функции DobavimVershinu(n)

Функция Risovat(g, x1, x2, y, dy) = (x1 + x2) / 2

Если (left != null), то

g.DrawLine(Pens.Blue, x, y, x - (x2 - x1) / 4, y

+ dy)

Все - Если

Если (right != null), то

g.DrawLine(Pens.Blue, x, y, x + (x2 - x1) / 4, y

+ dy)

Все - Если.FillEllipse(new SolidBrush(color), x - R, y - R, 2

* R, 2 * R).DrawEllipse(Pens.Black, x - R, y - R, 2 * R, 2 * R).DrawString(n.ToString(), new Font("Arial", 14),.Red, x-12, y-10)

Если (left != null), то.Risovat(g, x1, x, y + dy, dy)

Все - Если

Если (right != null), то

right.Risovat(g, x, x2, y + dy, dy)

Все - Если

Конец функции Risovat(g, x1, x2, y, dy)

Функция PoiskVeshiny(xm, ym, x1, x2, y, dy)

x = (x1 + x2) / 2

rasst = (число) Math.Sqrt((xm - x) * (xm - x) + (ym

y) * (ym - y))

Если (rasst <= R), то

Вернуть this

Все - Если

Если (xm < x), то

Если (left == null), то

Вернуть null

Иначе

Вернуть left.PoiskVeshiny(xm, ym, x1, x, y +

dy, dy)

Все - Если

Иначе

Если (right == null), то

Вернуть null

Иначе

Вернуть right.PoiskVeshiny(xm, ym, x, x2, y

+ dy, dy)

Все - Иначе

Конец функции PoiskVeshiny(xm, ym, x1, x2, y, dy)

Функция SetColor(color).color = color

Конец функции SetColor(color)

Функция GetN()

Вернуть n

Конец функции GetN()

Функция PoiskSummy(koren, s)= s - n= koren.PoiskVer(n1)

Если (v2 != null), то.SetColor(Color.Green).SetColor(Color.Green)

Вернуть истина

Все - Если

ok1 = ложь, ok2 = ложь

Если (left != null), то= left.PoiskSummy(koren, s)

Все - Если

Если (right != null), то

ok2 = right.PoiskSummy(koren, s)

Все - Если

Вернуть (ok1 || ok2)

Конец функции PoiskSummy(koren, s)

Функция PoiskVer(n1)

Если (n == n1), то

Вернуть this

Если (n1 < n), то

Если (left == null), то

Вернуть null

Иначе

Вернуть left.PoiskVer(n1)

Все - Если

Иначе

Если (right == null), то

Вернуть null

Иначе

Вернуть right.PoiskVer(n1)

Все - Иначе

Все - Иначе

Конец функции PoiskVer(n1)

Класс Tree

koren

Функция Tree()

koren = null

Конец функции Tree()

Функция DobavimVershinu(n)

Если (koren == null), то

koren = новый Verhina(n)

Иначе

koren.DobavimVershinu(n)

Конец функции DobavimVershinu(n)

Функция Risovat(g, x1, x2, y0, dy)

Если (koren == null), то

Вернуть

koren.Risovat(g, x1, x2, y0, dy)

Конец функции Risovat(g, x1, x2, y0, dy)

Функция PoiskVeshiny(xm, ym, x1, x2, y, dy)

Если (koren == null), то

Вернуть null

Вернуть koren.PoiskVeshiny(xm, ym, x1, x2, y, dy)

Конец функции PoiskVeshiny(xm, ym, x1, x2, y, dy)

Функция PoiskPary(s)= koren.PoiskSummy(koren, s)

Если (ok == ложь)

Вывод окна("Такая пара вершин не найдена!",

"Ошибка", MessageBoxButtons.OK,.Error)

Все - Если

Конец функции PoiskPary(s)

Конец класса Tree

3.2 Form1.cs

Класс Form1 : Form= 60= 75= 0

Функция Form1()()= новый Tree()1 = null

Конец функции Form1()

Функция toolStripButton1_Click(sender, e)

Строка n = toolStripTextBox1.Text= 0

Попытаться

z = Перевод в числовой формат(n)

Все - Попытаться

Поймать (Ошибку ex)

Вывод окна(ex.Message)

Вернуть

Все - Поймать

derevo.DobavimVershinu(z).Invalidate()

Конец функции toolStripButton1_Click(sender, e)

Функция Form1_Paint(sender, e)= this.CreateGraphics().Clear(Color.WhiteSmoke)= this.ClientSize.Width.Risovat(g, x1, x2, y0, dy)

Конец функции Form1_Paint(sender, e)

Функция Form1_MouseDown(sender, e)= this.ClientSize.Width= derevo.PoiskVeshiny(e.X, e.Y, x1, x2, y0, dy)

Если (v1 == null), то

Вывод окна("Вершина не найдена!", "Ошибка",

MessageBoxButtons.OK, MessageBoxIcon.Error);

Вернуть

Все - Если

v1.SetColor(Color.Yellow).PoiskPary(v1.GetN())()

Конец функции Form1_MouseDown(sender, e)

Конец класса Form1 : Form

4. Результаты выполнения программы

Введена буква

Ввод одинаковых вершин

Ввод дерева

Нажали мимо вершины

Выполнение задания

Выполнение задания

Пара вершин дающих сумму не найдена

6. Приложения

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

6.1 Tree.cs

System;

using System.Collections.Generic;System.Linq;System.Text;System.Drawing;System.Windows.Forms;Курсовая_Вар_16

{Verhina

{int R = 20;n;left;right;color;Verhina(int n)

{.n = n;= right = null;= Color.White;

}void DobavimVershinu(int n)

{(n == this.n)

{.Show("Такая вершина уже есть!",

"Ошибка", MessageBoxButtons.OK,.Error);;

}(n < this.n)

{(left == null)= new Verhina(n);.DobavimVershinu(n);

}

{(right == null)= new Verhina(n);.DobavimVershinu(n);

}

}void Risovat(Graphics g, int x1, int x2, int y,dy)

{x = (x1 + x2) / 2;(left != null)

{.DrawLine(Pens.Blue, x, y, x - (x2 - x1) / 4, y

+ dy);

}(right != null)

{.DrawLine(Pens.Blue, x, y, x + (x2 - x1) / 4, y

+ dy);

}.FillEllipse(new SolidBrush(color), x - R, y - R, 2

* R, 2 * R);.DrawEllipse(Pens.Black, x - R, y - R, 2 * R, 2 *);.DrawString(n.ToString(), new Font("Arial", 14),.Red, x-12, y-10);(left != null)

{.Risovat(g, x1, x, y + dy, dy);

}(right != null)

{.Risovat(g, x, x2, y + dy, dy);

}

}Verhina PoiskVeshiny(int xm, int ym, int x1,x2, int y, int dy)

{x = (x1 + x2) / 2;rasst = (int) Math.Sqrt((xm - x) * (xm - x) +

(ym - y) * (ym - y));(rasst <= R)

{this;

}(xm < x)

{(left == null)null;left.PoiskVeshiny(xm, ym, x1, x, y +, dy);

}

{(right == null)null;right.PoiskVeshiny(xm, ym, x, x2, y +, dy);

}

}void SetColor(Color color)

{.color = color;

}int GetN()

{n;

}bool PoiskSummy(Verhina koren, int s)

{n1 = s - n;v2 = koren.PoiskVer(n1);(v2 != null)

{.SetColor(Color.Green);.SetColor(Color.Green);true;

}ok1=false, ok2=false;(left != null)

{= left.PoiskSummy(koren, s);

}(right != null)

{= right.PoiskSummy(koren, s);

}(ok1 || ok2);

}Verhina PoiskVer(int n1)

{(n == n1)this;(n1 < n)

{(left == null)null;left.PoiskVer(n1);

}

{(right == null)null;right.PoiskVer(n1);

}

}

}Tree

{koren;Tree()

{= null;

}void DobavimVershinu(int n)

{(koren == null)= new Verhina(n);.DobavimVershinu(n);

}void Risovat(Graphics g, int x1, int x2, int, int dy)

{(koren == null);.Risovat(g, x1, x2, y0, dy);

}Verhina PoiskVeshiny(int xm, int ym, int x1,x2, int y, int dy)

{(koren == null)null;koren.PoiskVeshiny(xm, ym, x1, x2, y, dy);

}void PoiskPary(int s)

{ok = koren.PoiskSummy(koren, s);

if (ok == false)

{.Show("Такая пара вершин не найдена!",

"Ошибка", MessageBoxButtons.OK,.Error);

}

}

}

}

Оглавление . ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ 2. Теоретический материал по используемым динамическими структурам данных и средствам разработки приложений

Больше работ по теме: