sd_5

2

3

1 Введение

Целью работы является реализация бинарного дерева при помощи динамических структур. Программа будет разработана на языке программирования C#.

Задание

Реализовать бинарное дерево поиска при помощи динамических структур

(классы). Предусмотреть следующие интерфейсные методы:

1.Инициализация пустого дерева.

2.Добавление элемента в дерево.

3.Удаление элемента из дерева.

4.Очистка дерева.

5.Вывод дерева.

Вариант 8. Реализуйте метод, находящий самый большой и самый маленький элемент в дереве.

4

2 Основная часть

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

Листья – это последние узлы на дереве.

Листинг программы представлен в Приложении А.

2.1 Описание класса Tree

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

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

Рисунок 2.1.1 – Метод AddItem

5

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

Рисунок 2.1.2-Метод LevelOrderTraversal

При выводе проверяется есть ли корневой элемент, если нет, то выводится «Дерево пустое»

Рисунок 2.1.3-Метод Print

6

2.2 Описание реализации варианта

Для нахождения самого большого элемента и теории мы должны найти самый крайний правый элемент, а наименьший элемент соответственно крайний левый.

Исходя из теоритических сведений приведенных выше был написан метод (MaxMin), который перебирает значения до тех пор, пока не найдет самый правый лист бинарного дерева, а также самый левый лист.

Рисунок 2.2 – Метод MaxMin

7

2.3 Удаление элемента из дерева

Рисунок 2.3 – Фрагмент метода RemoveItem

Если удаляемый элемент не содержит левого поддерева, на его место становится следующий элемент от правого поддерева.

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

8

Рисунок 2.3.1 – Фрагмент метода RemoveItem

2.4 Демонстрация работы программы

Листинг программы приведен в Приложении А Демонстрация работы программы представлена на рисунке 2.4.

Рисунок 2.4– Демонстрация работы программы

9

Заключение

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

10

Приложение А (обязательное)

using System;

using System.Collections.Generic;

namespace sd5

{

class Program

{

static void Main(string[] args)

{

var tree = new Tree<int>();

Console.Write("Ввод кол-ва элементов дерева:\n"); int N = Convert.ToInt32(Console.ReadLine()); Console.Write("Ввод элементов дерева:\n");

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

{

int L = Convert.ToInt32(Console.ReadLine()); tree.AddItem(L);

}

tree.Print();

Console.Write("Ввод удаляемого элемента:\n"); int Z = Convert.ToInt32(Console.ReadLine()); tree.RemoveItem(Z);

Console.Write("Дерево после удаления:\n"); tree.Print();

int[] A = tree.MaxMin(); Console.WriteLine($"Max: {A[0]}"); Console.WriteLine($"Min: {A[1]}"); tree.Clear();

tree.Print();

}

}

class Node<T> : IComparable<T>, IComparable where T : IComparable, IComparable<T>

{

public T Data { get; set; }

public Node<T> Left { get; set; } public Node<T> Right { get; set; } public Node(T data)

{

Data = data;

}

public Node<T> Parent { get; set; }

public Node(T data, Node<T> parent)