СоХабр закрыт.
С 13.05.2019 изменения постов больше не отслеживаются, и новые посты не сохраняются.
Всем привет! Сегодня мы вспомним азы программирования на C# и повторим, что такое бинарные деревья, чем они отличаются от остальных деревьев, что же такое обход и какой он бывает.
Для начала повторим самое основное. Дерево – связный граф без циклов. Корень – самая верхняя вершина дерева. Лист – вершина, не имеющая потомков. Обход дерева – систематический просмотр всех вершин, при котором каждая вершина встречается один раз.
В рассматриваемых алгоритмах используется бинарное дерево – то есть дерево, в котором каждая вершина имеет два потомка (правые и левые поддеревья – left и right). Добавление реализуется по следующей схеме: при добавлении каждой новой вершины, если значение меньше корня, то оно записывается в левое поддерево, в противном случае – в правое (древесная сортировка).
Реализуем же все перечисленные алгоритмы на языке C#!
Тех, кто хочет немного обновить в памяти данный материал, либо еще только учится программировать базовые алгоритмы, без которых не обойдется ни один программист, прошу под кат!) Все фрагменты кода подробно прокомментированы, а демонстрационный проект на языке C# (VS2012) опубликован на GitHub.
Опишем класс Tree на языке C#:
public class Tree
{
// подкласс "элемент дерева"
public class TreeNode
{
public int Value; // численное значение
public int Count = 0; // сколько раз было добавлено данное численное значение
public TreeNode Left; // левое поддерево
public TreeNode Right; // правое поддерево
}
public TreeNode Node; // экземпляр класса "элемент дерева"
}
// добавление значения в дерево (рекурсивно)
private void AddRecursion(ref TreeNode node, int val)
// печать дерева (рекурсивно)
private void PrintRecursion(TreeNode node, int spaces, ref string s)
// обход дерева в ширину (итерационно, используется очередь)
private void Across(TreeNode node, ref string s, bool detailed)
// прямой обход (CLR - center, left, right)
private void CLR(TreeNode node, ref string s, bool detailed)
// обратный обход (LCR - left, center, right)
private void LCR(TreeNode node, ref string s, bool detailed)
// концевой обход (RCL - left, right, center)
private void RCL(TreeNode node, ref string s, bool detailed)
// прямой обход (CLR - center, left, right)
private void CLR(TreeNode node, ref string s, bool detailed)
{
/*
Аргументы метода:
1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке)
2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
*/
if (node != null)
{
if (detailed)
s += " получили значение " + node.Value.ToString() + Environment.NewLine;
else
s += node.Value.ToString() + " "; // запомнить текущее значение
if (detailed) s += " обходим левое поддерево" + Environment.NewLine;
CLR(node.Left, ref s, detailed); // обойти левое поддерево
if (detailed) s += " обходим правое поддерево" + Environment.NewLine;
CLR(node.Right, ref s, detailed); // обойти правое поддерево
}
else if (detailed) s += " значение отсутствует - null" + Environment.NewLine;
}
// обратный обход (LCR - left, center, right)
private void LCR(TreeNode node, ref string s, bool detailed)
{
/*
Аргументы метода:
1. TreeNode node - текущий "элемент дерева" (ref - передача по ссылке)
2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
*/
if (node != null)
{
if (detailed) s += " обходим левое поддерево" + Environment.NewLine;
LCR(node.Left, ref s, detailed); // обойти левое поддерево
if (detailed)
s += " получили значение " + node.Value.ToString() + Environment.NewLine;
else
s += node.Value.ToString() + " "; // запомнить текущее значение
if (detailed) s += " обходим правое поддерево" + Environment.NewLine;
LCR(node.Right, ref s, detailed); // обойти правое поддерево
}
else if (detailed) s += " значение отсутствует - null" + Environment.NewLine;
}
// концевой обход (RCL -right, center, left)
private void RCL(TreeNode node, ref string s, bool detailed)
{
/*
Аргументы метода:
1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке)
2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
*/
if (node != null)
{
if (detailed) s += " обходим правое поддерево" + Environment.NewLine;
RCL(node.Right, ref s, detailed); // обойти правое поддерево
if (detailed)
s += " получили значение " + node.Value.ToString() + Environment.NewLine;
else
s += node.Value.ToString() + " "; // запомнить текущее значение
if (detailed) s += " обходим левое поддерево" + Environment.NewLine;
RCL(node.Left, ref s, detailed); // обойти левое поддерево
}
else if (detailed) s += " значение отсутствует - null" + Environment.NewLine;
}
// обход дерева в ширину (итерационно, используется очередь)
private void Across(TreeNode node, ref string s, bool detailed)
{
/*
Аргументы метода:
1. TreeNode node - текущий "элемент дерева" (ref передача по ссылке)
2. ref string s - строка, в которой накапливается результат (ref - передача по ссылке)
*/
var queue = new Queue<TreeNode>(); // создать новую очередь
if (detailed) s += " заносим в очередь значение " + node.Value.ToString() + Environment.NewLine; queue.Enqueue(node); // поместить в очередь первый уровень
while (queue.Count!=0) // пока очередь не пуста
{
//если у текущей ветви есть листья, их тоже добавить в очередь
if (queue.Peek().Left != null)
{
if (detailed) s += " заносим в очередь значение " + queue.Peek().Left.Value.ToString() + " из левого поддерева" + Environment.NewLine;
queue.Enqueue(queue.Peek().Left);
}
if (queue.Peek().Right != null)
{
if (detailed) s += " заносим в очередь значение " + queue.Peek().Right.Value.ToString() + " из правого поддерева" + Environment.NewLine;
queue.Enqueue(queue.Peek().Right);
}
//извлечь из очереди информационное поле последнего элемента
if (detailed) s += " извлекаем значение из очереди: " + queue.Peek().Value.ToString() + Environment.NewLine;
else s += queue.Peek().Value.ToString() + " "; // убрать последний элемент очереди
queue.Dequeue();
}
}
комментарии (10)