1) 9
2) 9
|
2
3) 9
/ \
2 7
4) 9
/ \
2 7
\
8
5) 9
/ \
2 7
\ \
4 8
6) 9
/ \
2 7
/ \ \
0 4 8
как создать бинарное дерево на С#
подскажите как создать бинарное дерево на С# без библиотек, если возможно с комментариями
Потом создаешь класс "Дерево", в котором хранишь ссылку на элемент типа "Вершина дерева". Это будет корнем. А от корня уже можно плясать как хочешь.
Код специально не пишу, потому что вроде как тут все понятно, если тебе знакомы понятия "класс" и "ссылка".
Собственно, так создается бинарное дерево на многих (всех?) ООП-языках.
я то понимаю суть дерева, реализовать не знаю как (
Код:
class Node
{
public Node Left {get; set; }
public Node Right {get; set; }
public int Value {get; set; }
}
{
public Node Left {get; set; }
public Node Right {get; set; }
public int Value {get; set; }
}
Код:
class Tree
{
private Node _root;
Tree()
{
_root = new Node();
}
}
{
private Node _root;
Tree()
{
_root = new Node();
}
}
Вот создание дерева. Что здесь непонятного? Или непонятно, как его рекурсивно обходить?
не ясно как можно добавлять новые элементы и чтобы при добавлены элементов создавалось дерево, а не только в одну сторону добавлялись элементы.
Цитата: roman@
не ясно как можно добавлять новые элементы и чтобы при добавлены элементов создавалось дерево, а не только в одну сторону добавлялись элементы.
Слишком абстрактно говоришь. Я сам должен догадываться, какую задачу тебе нужно решить?
В интернетах и учебниках есть множество примеров. Самый известный и простой из них - построение бинарного дерева поиска. На вход поступает массив чисел, по нему строится дерево(по принципу: в вершине элемент, в левой подвершине меньшее число, в правой - большее).
Пример: 9,2,7,8,4, 0. Последовательно их засовываем в дерево по шагам:
Код:
Теперь понятно? Или код надо написать? Если и код не сможешь написать, лучше сразу скажи, какая у тебя задача, на ней будем рассматривать проблемы.
очень благодарен, что ты откликнулся)
пытаюсь создать дерево, чтобы последовательно заполнять все ветки новыми элементами которые добавляются
Создается класс-generic для бинарного дерева, туда можно впихнуть все, что можно сравнить(реализует интерфейс IComparable), а также создается конкретный класс (для демонстрации обхода дерева). Рекомендуется код вставить в студию и поизучать(его там тупо будет легче читать).
Код:
/// <summary>
/// Класс для одной вершины дерева
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
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;
}
}
/// <summary>
/// Общее дерево для сортировки элементов
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
class Tree<T> where T: IComparable
{
/// <summary>
/// Постоянная ссылка на корень. Нужна, чтобы не "потярть" дерево и служит точкой отсчет при рекурсивных обходах
/// </summary>
protected Node<T> _root;
/// <summary>
/// Метод служит для добавления нового элемента в дерево
/// </summary>
/// <param name="newElement">Новый элемент</param>
public void AddElement(T newElement)
{
if (_root == null) //Добавление первого элемента, своего рода инициализация дерева
{
//Так как дерево пустое, то просто инициализируем корень, без всяких проверок и вычислений
_root = new Node<T>(newElement);
return;
}
//Если корень уже есть, то заходим в него и начинаем вычислять, куда добавить текущий элемент
AddElementRecursion(_root, newElement);
}
/// <summary>
/// Рекурсивный метод для добавления элемента в дерево
/// Рассматривается текущая вершина currentNode и анализируется, куда надо добавлять новый элемент, в левое или правое поддерево
/// </summary>
/// <param name="currentNode">Текущая вершина</param>
/// <param name="newElement">Добавляемый элемент</param>
private static 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);
}
}
/// <summary>
/// Пример использования дерева. Поиск минимального элемента
/// </summary>
/// <returns>Найденный минимальный элемент</returns>
public T GetMinElement()
{
//указываем, что надо начинать искать с корня, и уходим в рекурсию
return GetMinElementRecursion(_root);
}
/// <summary>
/// Рекурсивный метод для поиска минимального элемента в дереве
/// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
/// </summary>
/// <param name="currentNode">Текущая вершина</param>
/// <returns>Найденный минимальный элемент</returns>
private static T GetMinElementRecursion(Node<T> currentNode)
{
if (currentNode.Left == null)
return currentNode.Element;
else
return GetMinElementRecursion(currentNode.Left);
}
}
/// <summary>
/// Конкретизированное дерево на тип double, расширяем предыдущее дерево
/// </summary>
class TreeDoubleType : Tree<double>
{
/// <summary>
/// Пример рекурсивного обхода дерева. Поиск суммы всех элементив
/// </summary>
/// <returns>Найденная сумма всех элементов</returns>
public double GetSum()
{
//Инициализация суммы
double sum = 0;
//Уход в рекурсию для поиска суммы
GetSumRecursion(_root, ref sum);
return sum;
}
/// <summary>
/// Рекурсивный метод для поиска минимального элемента в дереве
/// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
/// <param name="currentNode">Текущая вершина</param>
/// <param name="sum">Текущая сумма</param>
/// </summary>
private static void GetSumRecursion(Node<double> currentNode, ref double sum)
{
//Прибавляем элемент из текущей вершины
sum += currentNode.Element;
//Считаем сумму для левого поддерева
if (currentNode.Left != null)
GetSumRecursion(currentNode.Left, ref sum);
//Считаем сумму для левого поддерева
if (currentNode.Right != null)
GetSumRecursion(currentNode.Right, ref sum);
}
}
//Далее использование дерева, вставлять куда необходимо :)
//Массив, взятый из головы для примера
double[] doubleArray = new [] {1, 5, -1.4, 7, 3, 0, 4, -1, 6, 10, 8.4, 5, -7, -6, 5, 3, 7, -2};
//Создание дерева
TreeDoubleType tree = new TreeDoubleType();
//Заполнение дерева
foreach (double d in doubleArray)
tree.AddElement(d);
//Работа с деревом
double min = tree.GetMinElement();
double sum = tree.GetSum();
Console.WriteLine("Минимальный элемент дерева: {0}", min);
Console.WriteLine("Сумма элементов дерева: {0}", sum);
/// Класс для одной вершины дерева
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
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;
}
}
/// <summary>
/// Общее дерево для сортировки элементов
/// </summary>
/// <typeparam name="T">Элемент дерева. Сюда можно вставить всё, что можно сравнить =)</typeparam>
class Tree<T> where T: IComparable
{
/// <summary>
/// Постоянная ссылка на корень. Нужна, чтобы не "потярть" дерево и служит точкой отсчет при рекурсивных обходах
/// </summary>
protected Node<T> _root;
/// <summary>
/// Метод служит для добавления нового элемента в дерево
/// </summary>
/// <param name="newElement">Новый элемент</param>
public void AddElement(T newElement)
{
if (_root == null) //Добавление первого элемента, своего рода инициализация дерева
{
//Так как дерево пустое, то просто инициализируем корень, без всяких проверок и вычислений
_root = new Node<T>(newElement);
return;
}
//Если корень уже есть, то заходим в него и начинаем вычислять, куда добавить текущий элемент
AddElementRecursion(_root, newElement);
}
/// <summary>
/// Рекурсивный метод для добавления элемента в дерево
/// Рассматривается текущая вершина currentNode и анализируется, куда надо добавлять новый элемент, в левое или правое поддерево
/// </summary>
/// <param name="currentNode">Текущая вершина</param>
/// <param name="newElement">Добавляемый элемент</param>
private static 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);
}
}
/// <summary>
/// Пример использования дерева. Поиск минимального элемента
/// </summary>
/// <returns>Найденный минимальный элемент</returns>
public T GetMinElement()
{
//указываем, что надо начинать искать с корня, и уходим в рекурсию
return GetMinElementRecursion(_root);
}
/// <summary>
/// Рекурсивный метод для поиска минимального элемента в дереве
/// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
/// </summary>
/// <param name="currentNode">Текущая вершина</param>
/// <returns>Найденный минимальный элемент</returns>
private static T GetMinElementRecursion(Node<T> currentNode)
{
if (currentNode.Left == null)
return currentNode.Element;
else
return GetMinElementRecursion(currentNode.Left);
}
}
/// <summary>
/// Конкретизированное дерево на тип double, расширяем предыдущее дерево
/// </summary>
class TreeDoubleType : Tree<double>
{
/// <summary>
/// Пример рекурсивного обхода дерева. Поиск суммы всех элементив
/// </summary>
/// <returns>Найденная сумма всех элементов</returns>
public double GetSum()
{
//Инициализация суммы
double sum = 0;
//Уход в рекурсию для поиска суммы
GetSumRecursion(_root, ref sum);
return sum;
}
/// <summary>
/// Рекурсивный метод для поиска минимального элемента в дереве
/// Рассматривается текущая вершина currentNode и анализируется, где дальше надо искать минимальный элемента, в левом или правом поддереве
/// <param name="currentNode">Текущая вершина</param>
/// <param name="sum">Текущая сумма</param>
/// </summary>
private static void GetSumRecursion(Node<double> currentNode, ref double sum)
{
//Прибавляем элемент из текущей вершины
sum += currentNode.Element;
//Считаем сумму для левого поддерева
if (currentNode.Left != null)
GetSumRecursion(currentNode.Left, ref sum);
//Считаем сумму для левого поддерева
if (currentNode.Right != null)
GetSumRecursion(currentNode.Right, ref sum);
}
}
//Далее использование дерева, вставлять куда необходимо :)
//Массив, взятый из головы для примера
double[] doubleArray = new [] {1, 5, -1.4, 7, 3, 0, 4, -1, 6, 10, 8.4, 5, -7, -6, 5, 3, 7, -2};
//Создание дерева
TreeDoubleType tree = new TreeDoubleType();
//Заполнение дерева
foreach (double d in doubleArray)
tree.AddElement(d);
//Работа с деревом
double min = tree.GetMinElement();
double sum = tree.GetSum();
Console.WriteLine("Минимальный элемент дерева: {0}", min);
Console.WriteLine("Сумма элементов дерева: {0}", sum);