C# и немного алгоритмики: binary trees (реализация, примеры)

Всем доброго дня! Давайте немного вспомним азы программирования на C# и повторим, что такое бинарные деревья (binary trees), чем они отличаются от остальных деревьев, что же такое «обход» и каким он бывает.

Данная статья пригодится студентам, начинающим программистам, а также «профи» в качестве справочного материала. Приведены примеры, фрагменты алгоритмов и полный проект на 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). Сначала берется значение корня, затем обходится левое поддерево, затем правое;
• Концевой обход (RCL – right, center, left). Сначала обходится правое поддерево, затем берется значение корня, затем левое;
• Обратный обход (LCR – left, center, right). Сначала обходится левое поддерево, затем берется значение корня, затем правое поддерево.

Программная реализация всех трех перечисленных алгоритмов схожа, используется рекурсивный вызов методов. Сложность алгоритма O(N*log2(N)), где N – число вершин.

Прямой обход:

// прямой обход (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;
}

?

Обход в ширину

Поддеревья посещаются уровень за уровнем, каждый уровень обходится слева направо. Сложность алгоритма O(V+E), где V – множество вершин, а E-множество дуг.

// обход дерева в ширину (итерационно, используется очередь)
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();
    }
}?

С использованием данных методов я по-быстрому написал такую вот небольшую программку:

Разберем несколько примеров

Пример 1

Пример: дерево с большим числом поддеревьев, «правых» и «левых».
В глубину CLR: 5 4 3 1 9 8 6 7 15 10
В глубину LCR: 1 3 4 5 6 7 8 9 10 15
В глубину RCL: 15 10 9 8 7 6 5 4 3 1
В ширину: 5 4 9 3 8 15 1 6 10 7

Пример2

Пример: только отрицательные значения в дереве.
В глубину CLR: -2 -4 -15 -5 -1
В глубину LCR: -15 -5 -4 -2 -1
В глубину RCL: -1 -2 -4 -5 -15
В ширину: -2 -4 -1 -15 -5

Пример 3

Пример: отрицательные и положительные значения в дереве
В глубину CLR: 5 4 3 -30 0 1 2 15 8 30
В глубину LCR: -30 0 1 2 3 4 5 8 15 30
В глубину RCL: 30 15 8 5 4 3 2 1 0 -30
В ширину: 5 4 15 3 8 30 -30 0 1 2

Пример 4

Пример: только правые поддеревья
В глубину CLR: 4 5 6 7 8
В глубину LCR: 4 5 6 7 8
В глубину RCL: 8 7 6 5 4
В ширину: 4 5 6 7 8

Пример 5

Пример: только левые поддеревья
В глубину CLR: 10 9 8 7 6
В глубину LCR: 6 7 8 9 10
В глубину RCL: 10 9 8 7 6
В ширину: 10 9 8 7 6

Пример 6

Пример: наиболее емкая наглядность обходов
В глубину CLR: 10 9 11
В глубину LCR: 9 10 11
В глубину RCL: 11 10 9
В ширину: 10 9 11

Исходники проекта

Полные исходники программы для работы с бинарными деревьями выкладываю на GitHub. Можете свободно пользоваться ими для своих проектов или для более локальных задач, к примеру, выполнения лабораторных работ в университете. Присутствуют возможности загрузки исходных данных из текстового файла, сохранения результатов в файл, а также распечатки подробных действий реализации алгоритма (то есть логирование).

Спасибо за внимание! Если будут вопросы — рад на них ответить.

Автор: Dageron

Источник