СДлб5
.docxМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА
Отчет по практической работе №5 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС
Д.Р. Уразаев
Томск 2022
СОДЕРЖАНИЕ
Y
1 Введение 3
2 Ход работы 4
2.1 Описание класса Tree 4
2.2 Описание реализации варианта 6
2.3 Удаление элемента из дерева 7
2.4 Демонстрация работы программы 8
Заключение 10
1 Введение
Целью работы является реализация бинарного дерева при помощи динамических структур. Программа будет разработана на языке программирования C#.
Задание
Реализовать бинарное дерево поиска при помощи динамических структур (классы). Предусмотреть следующие интерфейсные методы:
Инициализация пустого дерева.
Добавление элемента в дерево.
Удаление элемента из дерева.
Очистка дерева.
Вывод дерева.
2 Ход работы
Дерево – это граф без петель и циклов. Деревья используются для организации данных в виде иерархической структуры. Первый узел дерева называется корнем. Если этот корневой узел соединен с другим узлом, тогда корень является родительским узлом, а связанный с ним узел – дочерним. Листья – это последние узлы на дереве.
Листинг программы представлен в Приложении А.
Описание класса Tree
Для добавления элемента в дерево используется метод AddItem. Он сравнивает значение добавляемого элемента с существующим, иесли значение элемента больше существующего, выполняется проверка на наличие правого поддерева, и, если оно отсутствует, элемент записывается вправо, иначе происходит вызов функции AddItem для следующего правого элемента.
Если же добавляемый элемент меньше существующего, выполняется проверка на наличие левого поддерева, и, если оно отсутствует, элемент записывается влево, иначе происходит вызов функции AddItem для следующего левого элемента.
Рисунок 2.1.1 – Метод AddItem
После удаления и обработки текущего элемента, в очередь помещаются два его дополнительных элемента.
Рисунок 2.1.2-Метод LevelOrderTraversal
При выводе проверяется есть ли корневой элемент, если нет, то выводится сообщение о том что дерево пустое
Рисунок 2.1.3-Метод Print
Описание реализации варианта
Для нахождения самого большого элемента и теории мы должны найти самый крайний правый элемент.
Исходя из теоритических сведений приведенных выше был написан метод (Maximum), который перебирает значения до тех пор, пока не найдет самый правый лист бинарного дерева.
Рисунок 2.2 – Метод Maximum
Удаление элемента из дерева
Рисунок 2.3 – Метод RemoveItem
Если удаляемый элемент не содержит левого поддерева, на его место становится следующий элемент от правого поддерева.
Если же элемент имеет поддеревья с обоих сторон, на его место становится наименьший элемент из правого поддерева.
Рисунок 2.3.1 – Метод RemoveItem
Демонстрация работы программы
Листинг программы приведен в Приложении А
Демонстрация работы программы представлена на рисунке 2.4.
Рисунок 2.4– Работа программы
Заключение
В результате практической работы был написан алгоритм реализации бинарного дерева в соответствии с заданным условием. Также был написан метод по нахождению максимального элемента дерева.
Приложение А (обязательное)
using System;
using System.Collections.Generic;
namespace sdlab5
{
class Program
{
static void Main(string[] args)
{
Random rnd = new Random();
var tree = new Tree<int>();
Console.Write("Entering the number of tree elements:\n");
int N = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < N; i++)
{
int L = rnd.Next(1, 50);
tree.AddItem(L);
}
tree.Print();
Console.Write("Entering the element to be removed:\n");
int Z = Convert.ToInt32(Console.ReadLine());
tree.RemoveItem(Z);
Console.Write("Tree after removal:\n");
tree.Print();
int[] A = tree.Maximum();
Console.WriteLine($"Max: {A[0]}");
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)
{
this.Data = data;
this.Parent = parent;
}
public bool AddItem(T val)
{
if (val.CompareTo(this.Data) < 0)
{
if (this.Left == null)
{
this.Left = new Node<T>(val, this);
}
else if (this.Left != null)
{
this.Left.AddItem(val);
}
}
else
{
if (this.Right == null)
{
this.Right = new Node<T>(val, this);
}
else if (this.Right != null)
{
this.Right.AddItem(val);
}
}
return true;
}
public int CompareTo(object obj)
{
if (obj is Node<T> item)
{
return Data.CompareTo(item);
}
else
{
throw new ArgumentException("Mismatch");
}
}
public int CompareTo(T other)
{
return Data.CompareTo(other);
}
public override string ToString()
{
return Data.ToString();
}
}
class Tree<T>
where T : IComparable, IComparable<T>
{
public Node<T> Root { get; set; }
public bool AddItem(T data)
{
if (Root == null)
{
Root = new Node<T>(data);
return true;
}
Root.AddItem(data);
return true;
}
public IEnumerable<Node<T>> LevelOrderTraversal()
{
if (Root == null)
{
yield break;
}
var ochered = new Queue<Node<T>>();
ochered.Enqueue(Root);
while (ochered.Count > 0)
{
var node = ochered.Dequeue();
yield return node;
if (node.Left != null)
{
ochered.Enqueue(node.Left);
}
if (node.Right != null)
{
ochered.Enqueue(node.Right);
}
}
}
public void Print()
{
if (Root == null)
{
Console.WriteLine("The tree is empty");
}
foreach (var item in LevelOrderTraversal())
{
Console.Write(item + ", ");
}
Console.WriteLine();
}
public void Clear()
{
Root = null;
}
private Node<T> Searching(Node<T> node, T val)
{
if (node == null) return null;
switch (val.CompareTo(node.Data))
{
case 1: return Searching(node.Right, val);
case -1: return Searching(node.Left, val);
case 0: return node;
default: return null;
}
}
List<T> enter = new List<T>();
public int[] Maximum()
{
var Max = this.Root;
var Max2 = this.Root;
while (Max.Right != null)
{
Max = Max.Right;
}
int[] f = { Convert.ToInt32(Max.Data), Convert.ToInt32(Max2.Data) };
return f;
}
public Node<T> Search(T val)
{
return Searching(this.Root, val);
}
public bool RemoveItem(T value)
{
Node<T> node = Search(value);
if (node == null)
{
return false;
}
Node<T> cTree;
if (node == this.Root)
{
if (node.Right != null)
{
cTree = node.Right;
}
else
{
cTree = node.Left;
}
while (cTree.Left != null)
{
cTree = cTree.Left;
}
T temp = cTree.Data;
this.RemoveItem(temp);
node.Data = temp;
return true;
}
if (node.Left == null && node.Right == null && this.Root != null)
{
if (node == node.Parent.Left)
{
node.Parent.Left = null;
}
else
{
node.Parent.Right = null;
}
return true;
}
if (node.Left != null && node.Right == null)
{
node.Left.Parent = node.Parent;
if (node == node.Parent.Left)
{
node.Parent.Left = node.Left;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = node.Left;
}
return true;
}
if (node.Left == null && node.Right != null)
{
node.Right.Parent = node.Parent;
if (node == node.Parent.Left)
{
node.Parent.Left = node.Right;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = node.Right;
}
return true;
}
if (node.Right != null && node.Right != null)
{
cTree = node.Right; while (cTree.Left != null)
{
cTree = cTree.Left;
}
if (cTree.Parent == node)
{
cTree.Left = node.Left;
node.Left.Parent = cTree;
cTree.Parent = node.Parent;
if (node == node.Parent.Left)
{
node.Parent.Left = cTree;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = cTree;
}
return true;
}
else
{
if (cTree.Right != null)
{
cTree.Right.Parent = cTree.Parent;
}
cTree.Parent.Left = cTree.Right;
cTree.Right = node.Right;
cTree.Left = node.Left;
node.Left.Parent = cTree;
node.Right.Parent = cTree;
cTree.Parent = node.Parent;
if (node == node.Parent.Left)
{
node.Parent.Left = cTree;
}
else if (node == node.Parent.Right)
{
node.Parent.Right = cTree;
}
return true;
}
}
return false;
}
}
}