.NET 2.x Составить описание класса для работы с бинарными деревьями поиска и реализовать основные операции - C#
Формулировка задачи:
Составить описание класса для работы с бинарными деревьями поиска (BST). Обеспечить выполнение основных операций: вставки, поиска и удаления элементов. Программа должна содержать меню, позволяющее осуществить вставку или добавление , поиск и удаления элемента.
Решение задачи: «.NET 2.x Составить описание класса для работы с бинарными деревьями поиска и реализовать основные операции»
textual
Листинг программы
class Program
{
public static void Main()
{
//создаем дерево людей:)
Tree<Human> tree = new Tree<Human>();
//список людишек
List<Human> humanList = new List<Human>()
{
new Human(30) { Name = "Bill"},
new Human(20) { Name = "John" },
new Human(16) { Name = "Быдло"},
new Human(19) { Name = "Красавчик"}
};
//добавляем людей в дерево
tree.AddElement(humanList);
//трай кетч, ибо метод обобщенный
try
{
var human = tree.GetElement(new Human(19));//ищем людишку по возрасту
Console.WriteLine("Искомый чувак по возрасту: {0}, Имя: {1}", 19 , human.Name);
}
catch (NotExistNodeExeption<Human> ex) //если чИлавека не существует в дереве
{
Console.WriteLine("Чувау с возрастом {0} не существет в дереве", ex.Element);
}
Console.ReadLine();
}
//наш класс человек
class Human : IComparable
{
public int Age { get; set; }
public string Name { get; set; }
public Human(int age)
{
Age = age;
}
//реализация интерфейса сравнения
public int CompareTo(object otherHuman)
{
Human human = otherHuman as Human;
if (Age < human.Age)
return -1;
else if (Age > human.Age)
return 1;
else
return 0;
}
public override string ToString()
{
return Age.ToString();
}
}
//класс елемента дерева
class Node<T> where T : IComparable
{
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public T Element { get; set; }
public Node(T element)
{
Element = element;
}
}
public class Tree<T> where T : IComparable
{
//верхушка дерева дерева
private Node<T> _root;
//добавление эл-та
public void AddElement(T newElement)
{
//если нет корня еще, то newElement становиься верхушкой
if (_root == null)
{
_root = new Node<T>(newElement);
return;
}
//Рекурсивное добавления
AddElementRecursion(_root, newElement);
}
//добавление массива ел-тов
public void AddElement(IEnumerable<T> newElements)
{
foreach (var newElement in newElements)
{
AddElement(newElement);
}
}
//тут все вроде ясно
private void AddElementRecursion(Node<T> currentNode, T newElement)
{
if (currentNode.Element.CompareTo(newElement) < 0)
{
if (currentNode.Right == null)
currentNode.Right = new Node<T>(newElement);
else
AddElementRecursion(currentNode.Right, newElement);
}
else
{
if (currentNode.Left == null)
currentNode.Left = new Node<T>(newElement);
else
AddElementRecursion(currentNode.Left, newElement);
}
}
//рекурсивный поиск эл.та
public T GetElement(T element)
{
return GetElementRecursion(_root, element);
}
//если нет ел-та в дереве, выбрасывается исключение
private T GetElementRecursion(Node<T> currentNode, T element)
{
if (currentNode == null)
throw new NotExistNodeExeption<T>(element);
else if (currentNode.Element.CompareTo(element) < 0)
return GetElementRecursion(currentNode.Right, element);
else if (currentNode.Element.CompareTo(element) > 0)
return GetElementRecursion(currentNode.Left, element);
else
return currentNode.Element;
}
}
//класс исключения, просто так запилил :)
public class NotExistNodeExeption<T> : Exception
{
public T Element { get; set; }
public NotExistNodeExeption(T element)
{
Element = element;
}
}
}